The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell ()

headers Matthew J. Williams | 3 Feb 2009 03:01

Dear All
	What would be the haskell equivalent of the C++ linked list complete 
with nodes? the list structure -- x:[} -- is the closest I've found.

	Sincerely
	Matthew J. Williams

On Tue, 03 Feb 2009 02:01:33 +0000, "Matthew J. Williams"
<matthewjwilliams1 <at> googlemail.com> wrote:
> Dear All
> 	What would be the haskell equivalent of the C++ linked list complete
> with nodes? the list structure -- x:[} -- is the closest I've found.
> 
> 	Sincerely
> 	Matthew J. Williams
> 

There are certainly some similarities between std::list from C++ and
Haskell's list, but there are also a lot of differences partly because C++
and Haskell are very different languages.

What properties of lists are you interested in comparing?

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

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

    http://www.haskell.org/haskellwiki/Tying_the_Knot

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
Beginners <at> haskell.org
http://www.haskell.org/mailman/listinfo/beginners

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.

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

2009/2/3 Brent Yorgey <byorgey <at> 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"

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.

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.
>

Mon	Tue	Wed	Thu	Fri	Sat	Sun

						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28

98	May 2013
198	April 2013
186	March 2013
173	February 2013
164	January 2013
180	December 2012
130	November 2012
138	October 2012
211	September 2012
208	August 2012
126	July 2012
148	June 2012
137	May 2012
227	April 2012
164	March 2012
106	February 2012
120	January 2012
176	December 2011
203	November 2011
261	October 2011
164	September 2011
330	August 2011
436	July 2011
486	June 2011
320	May 2011
200	April 2011
185	March 2011
161	February 2011
183	January 2011
232	December 2010
225	November 2010
182	October 2010
319	September 2010
294	August 2010
323	July 2010
230	June 2010
191	May 2010
216	April 2010
230	March 2010
290	February 2010
256	January 2010
255	December 2009
276	November 2009
217	October 2009
163	September 2009
125	August 2009
147	July 2009
134	June 2009
158	May 2009
246	April 2009
308	March 2009
242	February 2009
198	January 2009
86	December 2008
118	November 2008
117	October 2008
90	September 2008
86	August 2008
140	July 2008

linked lists

Re: linked lists

Circular Linked Lists

Re: Circular Linked Lists

Re: Circular Linked Lists

Re: Circular Linked Lists

Re: Circular Linked Lists

Re: Circular Linked Lists

Re: Circular Linked Lists

Re: Circular Linked Lists