Re: [Haskell-cafe] List spine traversal
> you will find it there but it's written in German. Yes. But at least there's an English abstract. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
Hi Andrew, you will find it there but it's written in German. http://opus.kobv.de/tuberlin/volltexte/2008/1755/ Regards, Martin. Andrew Hunter schrieb: 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
> 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. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
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 > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
On Mon, Jun 29, 2009 at 7:36 PM, Geoffrey Marchant wrote: > 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? 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 () -- ryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
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
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
On Sun, Jun 28, 2009 at 10:05 PM, 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? You can also use the combinators in Control.Parallel.Strategies. 'seqList r0' will force the spine, but you also can swap in different strategies to force evaluation on the elements as well. Prelude Control.Parallel.Strategies> let b = [ [1..n] | n <- [1..5] ] Prelude Control.Parallel.Strategies> :print b b = (_t1::[[Integer]]) Prelude Control.Parallel.Strategies> seqList r0 b () Prelude Control.Parallel.Strategies> :print b b = [(_t2::[Integer]),(_t3::[Integer]),(_t4::[Integer]), (_t5::[Integer]),(_t6::[Integer])] Prelude Control.Parallel.Strategies> seqList rwhnf b () Prelude Control.Parallel.Strategies> :print b b = [(1 : (_t7::[Integer])),(1 : (_t8::[Integer])), (1 : (_t9::[Integer])),(1 : (_t10::[Integer])), (1 : (_t11::[Integer]))] Prelude Control.Parallel.Strategies> seqList rnf b () Prelude Control.Parallel.Strategies> :print b b = [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]] I'm a newbie, but I believe that a typical usage would be something like: let myList = someExpression `using` seqList r0 where 'using' ensures traversal of the expression's spine. Graham ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
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
Re: [Haskell-cafe] List spine traversal
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
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
[Haskell-cafe] List spine traversal
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? -- Tony Morris http://tmorris.net/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
