[Haskell-cafe] Mux, was Re: Clearly, Haskell is ill-founded
Conor McBride
ctm at Cs.Nott.AC.UK
Thu Jul 19 06:03:45 EDT 2007
Hi Derek
On 17 Jul 2007, at 17:42, Derek Elkins wrote:
> On Tue, 2007-07-17 at 13:23 +0100, Conor McBride wrote:
>>
>> Mux...
>>
>>> data{-codata-} Mux x y = Mux (Muy x y)
>>
>> ...is defined by mutual induction with...
>>
>>> data Muy x y = y :- Muy x y | x :~ Mux y x
>
> As an inductive data type, isn't this empty?
Not in the manner which I intended. But it's a good question whether
what I
wrote unambiguously represented what I intended. In full-on nuspeak,
I meant
Mux = Nu mux. Mu muy. /\x y. Either (y, muy x y) (x, mux y x)
with the inductive definition nested inside the coinductive one, so that
we always eventually twist. Just once a summer, perhaps. I've basically
written Stefan's version, exploiting fixpoints at kind * -> * -> * to
deliver
the symmetry by the twisted :~ constructor.
As Apfelmus made rather more explicit, we have a coinductive sequence of
(nonempty inductive sequences which end with a twist). I was hoping to
signify this nesting by defining Mux to pack Muy, but I'm not sure
that's
a clear way to achieve the effect. With the Nu-Mu interpretation, the
fair
multiplexer is a coprogram:
mux :: Stream x -> Stream y -> Mux x y
mux (x :> xs) (y :> ys) = Mux (x :~ Mux (y :~ mux xs ys))
Nesting the other way around, we get this rather odd beast
Xum = Mu muy. Nu mux. /\x y. Either (y, muy x y) (x, mux y x)
which isn't empty either. Rather, it only allows finitely many uses
of :-
before it settles down to use :~ forever. That is, we eventually always
twist. So this way round allows the fair multiplexer, but not the
slightly
biased one which produces two xs for every y.
All of which goes to show that mixed co/programming is quite a sensitive
business, and it's easy to be too casual with notation.
All the best
Conor
More information about the Haskell-Cafe
mailing list