2009/6/29 Martijn van Steenbergen :

Tony Morris wrote:

...

Is there a canonical function for traversing the spine of a list?

I could use e.g. (seq . length) but this feels dirty, so I have foldl' (const . const $ ()) () which still doesn't feel right. What's the typical means of doing this?

(seq . length) doesn't sound that bad to me.

Martijn. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

What is the spine of a list? Google seems to fail me on this one. -- Deniz Dogan

I think I can see the point of forcing a list without forcing the actual data, but is there a way to do this that works on circular lists as well? On Mon, Jun 29, 2009 at 3:30 AM, Ketil Malde wrote:

Deniz Dogan writes:

...

What is the spine of a list? Google seems to fail me on this one.

A (single-linked) list can be seen as a set of cons cells, where each cell contains two pointers, one to the next cons cell, and one to the cell's data contents ('car' and 'cdr' in Lisp parlance).

The spine of the list is the cons cells and the next pointers, that is, the structure of the list, but not the actual data contained in it.

-k -- If I haven't seen further, it is by standing in the footprints of giants _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Mon, Jun 29, 2009 at 11:30 PM, Ryan Ingram 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? Are you certain that claim holds in the presence of seq? As a side note, (allowing seq and unsafePerformIO if necessary) is it possible to implement a map that preserves cycles (instead of transparently replacing them with infinite copies? Not horribly useful, but would be quite cute. AHH

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 wrote:

andrewhhunter:

...

On Mon, Jun 29, 2009 at 11:30 PM, Ryan Ingram 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

2009/7/1 Matthias Görgens :

...

As a side note, (allowing seq and unsafePerformIO if necessary) is it possible to implement a map that preserves cycles (instead of transparently replacing them with infinite copies?  Not horribly useful, but would be quite cute.

Baltasar Trancon y Widemann gave a talk on a generalized version of this problem at HaL4.  Short answer: The problem is tractable in theory, but you need heavy math.

Pretty cool--any paper/slides/transcript/video? AHH

you will find it there but it's written in German.

Yes. But at least there's an English abstract. Matthias.