Dear All
How would one mimic, in Haskell, a C++ circular linked list i.e.,
where the last element precedes (points to) the first?

Sincerely
Matthew J. Williams

_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

Matthew J. Williams wrote:

> How would one mimic, in Haskell, a C++ circular linked list i.e.,
> where the last element precedes (points to) the first?

Try this, "Tying the Knot":

[url]http://www.haskell.org/haskellwiki/Tying_the_Knot[/url]

Erik
--
--
-----------------------------------------------------------------
Erik de Castro Lopo
-----------------------------------------------------------------
"I consider C++ the most significant technical hazard to the survival
of your project and do so without apologies." -- Alistair Cockburn
_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

Matthew,

I would strongly suggest taking a look on SPJ's presentation at OSCON 2007
(video at [url]http://blip.tv/file/324976[/url]). He shows a very interesting circular
list (with a zipper).

Since you are interested in functional data structures, Chris Okasaki's book
"Purely Functional Data Structures" is a great source too!



On Tue, Feb 3, 2009 at 00:53, Erik de Castro Lopo
<mle+cl@mega-nerd.com<mle%2Bcl@mega-nerd.com>
> wrote:

> Matthew J. Williams wrote:
>
> > How would one mimic, in Haskell, a C++ circular linked list i.e.,
> > where the last element precedes (points to) the first?
>
> Try this, "Tying the Knot":
>
> [url]http://www.haskell.org/haskellwiki/Tying_the_Knot[/url]
>
> Erik
> --
> --
> -----------------------------------------------------------------
> Erik de Castro Lopo
> -----------------------------------------------------------------
> "I consider C++ the most significant technical hazard to the survival
> of your project and do so without apologies." -- Alistair Cockburn
> _______________________________________________
> Beginners mailing list
> [email]Beginners@haskell.org[/email]
> [url]http://www.haskell.org/mailman/listinfo/beginners[/url]
>



--
Rafael Gustavo da Cunha Pereira Pinto
Electronic Engineer, MSc.

_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

On Feb 2, 2009, at 9:45 PM, Matthew J. Williams wrote:

> Dear All
> How would one mimic, in Haskell, a C++ circular linked list i.e.,
> where the last element precedes (points to) the first?

You are getting deep answers to what is perhaps a simple question. You
haven't said exactly what you want to do with a circular linked list,
and people are perhaps fearing the trickiest applications.

Have you tried the Prelude function cycle?

> cycle :: [a] -> [a]
> cycle ties a finite list into a circular one, or equivalently, the
> infinite repetition of the original list. It is the identity on
> infinite lists.

For instance, in ghci one gets

> Prelude> [1..3]
> [1,2,3]
> Prelude> take 10 $ cycle [1..3]
> [1,2,3,1,2,3,1,2,3,1]

cycle doesn't actually construct in memory a cyclic data structure, as
one might in C. It's more like those repeat bars in sheet music.
_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

>
> cycle doesn't actually construct in memory a cyclic data structure, as one
> might in C. It's more like those repeat bars in sheet music.

It doesn't?

cycle xs = xs' where xs' = xs ++ xs'

That sure looks like a cyclic data structure to me! xs' references a
thunk which computes (xs ++ xs'); this thunk, in turn, references
xs'. cycle is memory-efficient precisely because it *does* actually
construct a cyclic data structure.

-Brent
_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

2009/2/3 Brent Yorgey <byorgey@seas.upenn.edu>:

>
> cycle xs = xs' where xs' = xs ++ xs'
>
> That sure looks like a cyclic data structure to me! xs' references a
> thunk which computes (xs ++ xs'); this thunk, in turn, references
> xs'. cycle is memory-efficient precisely because it *does* actually
> construct a cyclic data structure.

That's just magnificent!



--
"There is no way to peace; peace is the way"
_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

So the "repeat bars" are there until the first pass through the list
completes, otherwise cycle would be bottom on infinite lists.
Thereafter, you're saying that a core dump would reveal a completely
homogeneous memory representation, just like C code, that one could
pass through the foreign function interface to C code?

GHC seems to have a special awareness of cyclic lists. For example,
ghci computes

> (zip (cycle [1..3]) (cycle [1..4])) !! (1000^1000)

immediately, as if it knows enough to compute 1000^1000 mod 12, by
repeated squaring.

On Feb 3, 2009, at 9:17 AM, Brent Yorgey wrote:

> It doesn't?
>
> cycle xs = xs' where xs' = xs ++ xs'
>
> That sure looks like a cyclic data structure to me! xs' references a
> thunk which computes (xs ++ xs'); this thunk, in turn, references
> xs'. cycle is memory-efficient precisely because it *does* actually
> construct a cyclic data structure.

_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

Am Dienstag, 3. Februar 2009 15:54 schrieb Dave Bayer:
> So the "repeat bars" are there until the first pass through the list
> completes, otherwise cycle would be bottom on infinite lists.
> Thereafter, you're saying that a core dump would reveal a completely
> homogeneous memory representation, just like C code, that one could
> pass through the foreign function interface to C code?
>
> GHC seems to have a special awareness of cyclic lists. For example,
> ghci computes
>
> > (zip (cycle [1..3]) (cycle [1..4])) !! (1000^1000)

No, it's that the type of (!!) is [a] -> Int -> a, and 1000^1000 :: Int is 0.

>
> immediately, as if it knows enough to compute 1000^1000 mod 12, by
> repeated squaring.
>
> On Feb 3, 2009, at 9:17 AM, Brent Yorgey wrote:
> > It doesn't?
> >
> > cycle xs = xs' where xs' = xs ++ xs'
> >
> > That sure looks like a cyclic data structure to me! xs' references a
> > thunk which computes (xs ++ xs'); this thunk, in turn, references
> > xs'. cycle is memory-efficient precisely because it *does* actually
> > construct a cyclic data structure.
>

_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

On Tue, Feb 03, 2009 at 09:54:46AM -0500, Dave Bayer wrote:
> So the "repeat bars" are there until the first pass through the list
> completes, otherwise cycle would be bottom on infinite lists. Thereafter,
> you're saying that a core dump would reveal a completely homogeneous memory
> representation, just like C code, that one could pass through the foreign
> function interface to C code?

I'm not really sure what you mean by "repeat bars". There really is a
cyclic data structure in memory at all times--it's just that until the
first pass through the list, part of it is a thunk. After a complete
pass to the list, however, a core dump would indeed reveal something
like what you suggest.

>
> GHC seems to have a special awareness of cyclic lists. For example, ghci
> computes
>
>> (zip (cycle [1..3]) (cycle [1..4])) !! (1000^1000)
>
> immediately, as if it knows enough to compute 1000^1000 mod 12, by repeated
> squaring.

I came to the same conclusion as Daniel but it took me a few minutes
of puzzlement. Besides, it should actually be equal to (2,1), not
(1,1). =)

-Brent
_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

On Feb 3, 2009, at 10:04 AM, Daniel Fischer wrote:

>> GHC seems to have a special awareness of cyclic lists. For example,
>> ghci computes
>>
>>> (zip (cycle [1..3]) (cycle [1..4])) !! (1000^1000)
>
> No, it's that the type of (!!) is [a] -> Int -> a, and 1000^1000 ::
> Int is 0.
>
>>
>> immediately, as if it knows enough to compute 1000^1000 mod 12, by
>> repeated squaring.

Thanks.

The following takes forever, but it doesn't consume memory:

> Prelude> :m Data.List
> Prelude Data.List> genericIndex (zip (cycle [1..3]) (cycle [1..4]))
> (1000^1000)

So zip is doing something smart here with cyclic lists.

_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]