[Haskell-cafe] List spine traversal

[Ryan Ingram]

seq allows you to distinguish (undefined) from (const undefined)
case allows you to distinguish (undefined) from the pair (undefined, undefined)

   isFun f = f `seq` True
   isPair p = case p of (_,_) -> True


isFun undefined -> undefined
isFun (const undefined) -> True
isPair undefined -> undefined
isPair (undefined, undefined) -> True

I don't think either of these violate equational reasoning or
referential transparency, though.  You cannot treat a call to seq as
"flip const", though, it has to be a bit more magic than that.

You do get different bottoms, however; (length xs1 + length xs1) isn't
terminating, while (length xs2 + length xs2) will probably consume
your heap.  But that just means that you can distinguish them in IO,
which is allowed :)

  -- ryan


On Tue, Jun 30, 2009 at 1:38 PM, Don Stewart<dons at galois.com> wrote:
> andrewhhunter:
>> On Mon, Jun 29, 2009 at 11:30 PM, Ryan Ingram<ryani.spam at gmail.com> wrote:
>> > There can't be a way to do so that is pure, because such a function
>> > could distinguish between
>> >> xs1 = () : xs1
>> > and
>> >> xs2 = f () where f () = () : f ()
>> >
>>
>> But doesn't seq and friends cause many of our normal referential
>> transparency guarantees to be invalid?
>
> Equational reasoning, in the presence of bottoms, anyway.
>
> -- Don
>