Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. MD2 Implementation (Sean Bartell)
2. Re: folds again -- myCycle (7stud)
3. Hudak state emulation discussion - can you give me some
idea? (Girish Bhat)
4. Re: Re: folds again -- myCycle (Daniel Fischer)
5. Re: folds again -- myCycle (7stud)
----------------------------------------------------------------------
Message: 1
Date: Sun, 15 Mar 2009 23:33:18 -0400
From: Sean Bartell <[email protected]>
Subject: [Haskell-beginners] MD2 Implementation
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
I've just recently started learning Haskell, and I wrote an MD2
implementation. This version is correct, but crashes on large files
because of the weak evaluation. What I'm wondering is, what's the sort
of thought-process I would go through to find the problem areas and
fix it?
Also, please post any suggestions you have for this code, for style or
whatever :).
{-# LANGUAGE BangPatterns #-}
module MD2 (md2) where
import qualified Data.ByteString as B
import Data.Bits (xor)
import Data.List (foldl', mapAccumL)
import Data.Word (Word8)
table = B.pack [0x29, 0x2E, 0x43, 0xC9, 0xA2, 0xD8, 0x7C, 0x01,
0x3D, 0x36, 0x54, 0xA1, 0xEC, 0xF0, 0x06, 0x13,
0x62, 0xA7, 0x05, 0xF3, 0xC0, 0xC7, 0x73, 0x8C,
0x98, 0x93, 0x2B, 0xD9, 0xBC, 0x4C, 0x82, 0xCA,
0x1E, 0x9B, 0x57, 0x3C, 0xFD, 0xD4, 0xE0, 0x16,
0x67, 0x42, 0x6F, 0x18, 0x8A, 0x17, 0xE5, 0x12,
0xBE, 0x4E, 0xC4, 0xD6, 0xDA, 0x9E, 0xDE, 0x49,
0xA0, 0xFB, 0xF5, 0x8E, 0xBB, 0x2F, 0xEE, 0x7A,
0xA9, 0x68, 0x79, 0x91, 0x15, 0xB2, 0x07, 0x3F,
0x94, 0xC2, 0x10, 0x89, 0x0B, 0x22, 0x5F, 0x21,
0x80, 0x7F, 0x5D, 0x9A, 0x5A, 0x90, 0x32, 0x27,
0x35, 0x3E, 0xCC, 0xE7, 0xBF, 0xF7, 0x97, 0x03,
0xFF, 0x19, 0x30, 0xB3, 0x48, 0xA5, 0xB5, 0xD1,
0xD7, 0x5E, 0x92, 0x2A, 0xAC, 0x56, 0xAA, 0xC6,
0x4F, 0xB8, 0x38, 0xD2, 0x96, 0xA4, 0x7D, 0xB6,
0x76, 0xFC, 0x6B, 0xE2, 0x9C, 0x74, 0x04, 0xF1,
0x45, 0x9D, 0x70, 0x59, 0x64, 0x71, 0x87, 0x20,
0x86, 0x5B, 0xCF, 0x65, 0xE6, 0x2D, 0xA8, 0x02,
0x1B, 0x60, 0x25, 0xAD, 0xAE, 0xB0, 0xB9, 0xF6,
0x1C, 0x46, 0x61, 0x69, 0x34, 0x40, 0x7E, 0x0F,
0x55, 0x47, 0xA3, 0x23, 0xDD, 0x51, 0xAF, 0x3A,
0xC3, 0x5C, 0xF9, 0xCE, 0xBA, 0xC5, 0xEA, 0x26,
0x2C, 0x53, 0x0D, 0x6E, 0x85, 0x28, 0x84, 0x09,
0xD3, 0xDF, 0xCD, 0xF4, 0x41, 0x81, 0x4D, 0x52,
0x6A, 0xDC, 0x37, 0xC8, 0x6C, 0xC1, 0xAB, 0xFA,
0x24, 0xE1, 0x7B, 0x08, 0x0C, 0xBD, 0xB1, 0x4A,
0x78, 0x88, 0x95, 0x8B, 0xE3, 0x63, 0xE8, 0x6D,
0xE9, 0xCB, 0xD5, 0xFE, 0x3B, 0x00, 0x1D, 0x39,
0xF2, 0xEF, 0xB7, 0x0E, 0x66, 0x58, 0xD0, 0xE4,
0xA6, 0x77, 0x72, 0xF8, 0xEB, 0x75, 0x4B, 0x0A,
0x31, 0x44, 0x50, 0xB4, 0x8F, 0xED, 0x1F, 0x1A,
0xDB, 0x99, 0x8D, 0x33, 0x9F, 0x11, 0x83, 0x14]
-- NOTE: There's a problematic typo in RFC 1319 in section 3.2. It says
-- Set C[j] to S[c xor L], but it should be Set C[j] to C[j] xor S[c xor L].
type Block = B.ByteString
two x = (x, x)
applySnd f (x, y) = (x, f y)
zeroBlock = B.replicate 16 0
checksumInitial = (0, zeroBlock)
foldlBlocks :: (a -> Block -> a) -> a -> B.ByteString -> a
foldlBlocks f v x | B.null x = v
| otherwise = foldlBlocks f v' rest
where (block, rest) = B.splitAt 16 x
!v' = f v block
checksumBlock :: (Word8, Block) -> Block -> (Word8, Block)
checksumBlock (l, cs) bs = applySnd B.pack $ mapAccumL updateL l $ B.zip cs bs
where updateL l (c, b) = two $ c `xor` table `B.index`
fromIntegral (l `xor` b)
doBlock :: Block -> Block -> Block
doBlock ds bs = B.take 16 xs'
where xs = ds `B.append` bs `B.append` B.pack (B.zipWith xor ds bs)
(_, xs') = foldl' doRound (0, xs) [0..17]
doRound (t, xs) n = let (t', xs') = B.mapAccumL updateT t xs
in (t' + n, xs')
updateT t b = two $ b `xor` table `B.index` fromIntegral t
doBlockAndCS (csState, blockState) block = (checksumBlock csState
block, doBlock blockState block)
padding n = B.replicate n (fromIntegral n)
md2 :: B.ByteString -> Block
md2 bs = let padded = bs `B.append` padding (16 - B.length bs `mod` 16)
((_, cksum), state) = foldlBlocks doBlockAndCS
(checksumInitial, zeroBlock) padded
in doBlock state cksum
------------------------------
Message: 2
Date: Tue, 17 Mar 2009 01:24:39 +0000 (UTC)
From: 7stud <[email protected]>
Subject: [Haskell-beginners] Re: folds again -- myCycle
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> Let us rewrite the definition a little (looking only at the case for
> nonempty lists):
>
> Variant 1:
> myCycle xs = foldr leftAdd [] [1 .. ]
> where
> leftAdd _ acc = xs ++ acc
>
> foldr leftAdd [] [1 .. ]
> ~> leftAdd 1 (foldr leftAdd [] [2 .. ])
> ~> xs ++ (foldr leftAdd [] [2 .. ])
> ~> xs ++ (leftAdd 2 (foldr leftAdd [] [3 .. ]))
> ~> xs ++ (xs ++ (foldr leftAdd [] [3 .. ]))
> ~> xs ++ (xs ++ (xs ++ (xs ++ ...)))
>
> Variant 2:
> myCycle xs = foldr rightAdd [] [1 .. ]
> where
> rightAdd _ acc = acc ++ xs
>
> foldr rightAdd [] [1 .. ]
> ~> rightAdd 1 (foldr rightAdd [] [2 .. ])
> ~> (foldr rightAdd [] [2 .. ]) ++ xs
> ~> (rightAdd 2 (foldr rightAdd [] [3 .. ])) ++ xs
> ~> ((foldr rightAdd [] [3 .. ]) ++ xs) ++ xs
> ~> (((... ++ xs) ++ xs) ++ xs
>
Thanks for the explanation. After reading your post, I practiced writing
a few foldr's out by hand. It really helped me to understand what foldr
was doing. The part that initially confused me was the step in the third
line:
> foldr rightAdd [] [1 .. ]
> ~> rightAdd 1 (foldr rightAdd [] [2 .. ])
> ~> (foldr rightAdd [] [2 .. ]) ++ xs
In case any other beginner reads this thread and is confused by
that, here's what's going on. In RWH foldr is defined on p. 94
like this:
foldr step zero (x:xs) = step x (foldr step zero xs)
Daniel Fischer's example is calling foldr like this:
foldr rightAdd [] [1 .. ]
matching the foldr definition to that foldr function call:
foldr step zero (x:xs)
foldr rightAdd [] [1 .. ]
you can see that step is the function rightAdd, zero's value is [],
x = 1, and xs = [2..]. Therefore, from the definition of foldr:
foldr rightAdd [] [1..] = rightAdd 1 (foldr rightAdd [] [2..])
The right hand side of that equation is a function call to
rightAdd. It specifies two arguments: the first argument
is 1, and the second argument is the expression in the
parentheses. Now, look at the definition of rightAdd:
> rightAdd _ acc = acc ++ xs
rightAdd is a function that ignores its first argument,
then concatenates xs to the right side of its second
argument. Applying that to this function call:
rightAdd 1 (foldr rightAdd [] [2..])
rightAdd ignores the first argument, the 1, and
concatenates xs to the right side of its second
argument, which in this case is the expression
in parentheses, so you get:
(foldr rightAdd [] [2..]) ++ xs
Therefore:
rightAdd 1 (foldr rightAdd [] [2..]) =
(foldr rightAdd [] [2..]) ++ xs
Then it's just a matter of expanding the expression
in the parentheses a few more times until you understand
what the pattern is.
> Let us rewrite it a little more.
> Obviously, it doesn't matter which list is passed into
> foldr leftAdd []
> , as long as it's infinite. So instead of passing [1 .. ], let us pass a
> simpler infinite list, say
> ones = 1:ones
> (or ones = repeat 1).
> Then the evaluation becomes
>
> foldr leftAdd [] ones
> ~> foldr leftAdd [] (1:ones)
> ~> leftAdd 1 (foldr leftAdd [] ones)
> ~> xs ++ (foldr leftAdd [] ones)
>
> foldr rightAdd [] ones
> ~> foldr rightAdd [] (1:ones)
> ~> rightAdd 1 (foldr rightAdd [] ones)
> ~> (foldr rightAdd [] ones) ++ xs
>
> So variant 1 amounts to
> myCycle xs = let ys = xs ++ ys in ys
> and variant 2 to
> myCycle2 xs = let ys = ys ++ xs in ys
>
> Now it should be easy to see why the first works, but not the second.
>
No. I could tell from the example at the beginning of your post
that there was an infinite expression on the front of the result list, but
I can't see that in those equations. What am I failing to recognize there?
> And from the rewriting, we can read off another representation of
> cycle a fold.
> We have, for all lists ks, ms:
> ks ++ ms = foldr (:) ms ks
>
> So we can write variant 1 as the snappy
>
> myCycle xs = let ys = foldr (:) ys xs in ys
>
I can't understand that one. I'll have to write it out:
definition of foldr so I can refer to it:
foldr step zero (x:xs) = step x (foldr step zero xs)
myCycle2 [1, 2] =>
ys = foldr (:) ys [1, 2]
---------------
Here's the left hand side of the foldr definition:
foldr step zero (x:xs) =>match these parameters to the args in the call:
foldr (:) ys [1, 2] =
Now writing out what's on the right hand side of the equals sign in the foldr
definition using the args from the line above:
= (:) 1 (foldr (:) ys 2:[])
= 1:(foldr (:) ys 2:[])
Expand the term in the parentheses:
= 1:( (:) 2 (foldr (:) ys []) )
= 1:( 2:(foldr (:) ys []) )
= 1:2:(foldr (:) ys [])
= 1:2:(ys)
= 1:2:ys
But ys is defined to be:
foldr (:) ys [1, 2]
So substituting into the last line:
= 1:2:(foldr (:) ys [1, 2])
= 1:2:( (:) 1 (foldr (:) ys 2:[])
= 1:2:(1:(foldr (:) ys 2:[])
= 1:2:1:( (:) 2 (foldr (:) ys [])
= 1:2:1:( 2:(foldr (:) ys [])
= 1:2:1:2:(foldr (:) ys [])
= 1:2:1:2:(ys)
= 1:2:1:2:ys
But ys is defined to be:
foldr (:) ys [1, 2]
Therefore, that process goes on and on ad infinitum. Pretty slick.
I guess haskell thunks the whole infinite expression, therefore
the let expression:
let ys = ....
in ys
doesn't cause an infinite loop in the ys = ... line, which means
the second line executes, which means ys is returned as the
result of the function call myCycle2 [1,2]?
------------------------------
Message: 3
Date: Tue, 17 Mar 2009 14:32:24 +0530
From: Girish Bhat <[email protected]>
Subject: [Haskell-beginners] Hudak state emulation discussion - can
you give me some idea?
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=windows-1252
Hi Everyone,
I was going through the classic Hudak paper "Conception, Evolution,
and Application of Functional Programming".
Probably the most valuable part is towards the end where he talks
about how state is represented in Haskell.
On Page 48 of the PDF (page 406 of the ACM Computing survey volume),
he gives the following equations
"For expository purposes we would like to make the state as implicit
as possible, and thus we express the result as a composition of
higher-order functions. To facilitate this and to make the result look
as much like the original program as possible, we define the following
higher-order infix operators and functions":
1 f:=g =\s -> +fs(gs)
2 f;g =\s -> g(fs)=\s-+fs(gs)
3 f;g =\s -> g(fs)
4 goto f = f
5 f+g=\s-+fs+gs
6 f<g=\s-+fs<gs
7 if p c = \s + (if (p s) then (c s) else s)
Unfortunately I am unable to parse/understand what he is doing here.
My closure understanding too seems to be wonky. :)
Would someone be kind enough to translate each of the above into plain
english and explain how to read such eqns in the future?
thanks!
------------------------------
Message: 4
Date: Tue, 17 Mar 2009 12:28:35 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Re: folds again -- myCycle
To: 7stud <[email protected]>, [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Dienstag, 17. März 2009 02:24 schrieb 7stud:
> Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> > Let us rewrite the definition a little (looking only at the case for
> > nonempty lists):
> >
> > Variant 1:
> > myCycle xs = foldr leftAdd [] [1 .. ]
> > where
> > leftAdd _ acc = xs ++ acc
> >
> > foldr leftAdd [] [1 .. ]
> > ~> leftAdd 1 (foldr leftAdd [] [2 .. ])
> > ~> xs ++ (foldr leftAdd [] [2 .. ])
> > ~> xs ++ (leftAdd 2 (foldr leftAdd [] [3 .. ]))
> > ~> xs ++ (xs ++ (foldr leftAdd [] [3 .. ]))
> > ~> xs ++ (xs ++ (xs ++ (xs ++ ...)))
> >
> > Variant 2:
> > myCycle xs = foldr rightAdd [] [1 .. ]
> > where
> > rightAdd _ acc = acc ++ xs
> >
> > foldr rightAdd [] [1 .. ]
> > ~> rightAdd 1 (foldr rightAdd [] [2 .. ])
> > ~> (foldr rightAdd [] [2 .. ]) ++ xs
> > ~> (rightAdd 2 (foldr rightAdd [] [3 .. ])) ++ xs
> > ~> ((foldr rightAdd [] [3 .. ]) ++ xs) ++ xs
> > ~> (((... ++ xs) ++ xs) ++ xs
>
> Thanks for the explanation. After reading your post, I practiced writing
> a few foldr's out by hand. It really helped me to understand what foldr
> was doing. The part that initially confused me was the step in the third
>
> line:
> > foldr rightAdd [] [1 .. ]
> > ~> rightAdd 1 (foldr rightAdd [] [2 .. ])
> > ~> (foldr rightAdd [] [2 .. ]) ++ xs
>
Sorry. I was too lazy to write out the intermediate step. However, since that
resulted in you doing it manually and so getting more familiar with foldr, it
had a good effect :)
> In case any other beginner reads this thread and is confused by
> that, here's what's going on. In RWH foldr is defined on p. 94
> like this:
>
> foldr step zero (x:xs) = step x (foldr step zero xs)
>
> Daniel Fischer's example is calling foldr like this:
>
> foldr rightAdd [] [1 .. ]
>
> matching the foldr definition to that foldr function call:
>
> foldr step zero (x:xs)
> foldr rightAdd [] [1 .. ]
>
> you can see that step is the function rightAdd, zero's value is [],
> x = 1, and xs = [2..]. Therefore, from the definition of foldr:
>
> foldr rightAdd [] [1..] = rightAdd 1 (foldr rightAdd [] [2..])
>
> The right hand side of that equation is a function call to
> rightAdd. It specifies two arguments: the first argument
> is 1, and the second argument is the expression in the
>
> parentheses. Now, look at the definition of rightAdd:
> > rightAdd _ acc = acc ++ xs
>
> rightAdd is a function that ignores its first argument,
> then concatenates xs to the right side of its second
> argument. Applying that to this function call:
>
> rightAdd 1 (foldr rightAdd [] [2..])
>
> rightAdd ignores the first argument, the 1, and
> concatenates xs to the right side of its second
> argument, which in this case is the expression
> in parentheses, so you get:
>
> (foldr rightAdd [] [2..]) ++ xs
>
> Therefore:
>
> rightAdd 1 (foldr rightAdd [] [2..]) =
> (foldr rightAdd [] [2..]) ++ xs
>
> Then it's just a matter of expanding the expression
> in the parentheses a few more times until you understand
> what the pattern is.
>
> > Let us rewrite it a little more.
> > Obviously, it doesn't matter which list is passed into
> > foldr leftAdd []
> > , as long as it's infinite. So instead of passing [1 .. ], let us pass a
> > simpler infinite list, say
> > ones = 1:ones
> > (or ones = repeat 1).
> > Then the evaluation becomes
> >
> > foldr leftAdd [] ones
> > ~> foldr leftAdd [] (1:ones)
> > ~> leftAdd 1 (foldr leftAdd [] ones)
> > ~> xs ++ (foldr leftAdd [] ones)
> >
> > foldr rightAdd [] ones
> > ~> foldr rightAdd [] (1:ones)
> > ~> rightAdd 1 (foldr rightAdd [] ones)
> > ~> (foldr rightAdd [] ones) ++ xs
> >
> > So variant 1 amounts to
> > myCycle xs = let ys = xs ++ ys in ys
> > and variant 2 to
> > myCycle2 xs = let ys = ys ++ xs in ys
> >
> > Now it should be easy to see why the first works, but not the second.
>
> No. I could tell from the example at the beginning of your post
> that there was an infinite expression on the front of the result list, but
> I can't see that in those equations. What am I failing to recognize there?
Ah, well. I again underestimated how much experience one needs to see it
immediately, sorry once more.
The right hand side of myCycle2's definition (if we specialise xs to, say,
[1,2,3]) is basically the same as a definition
ys = ys ++ [1,2,3]
at top level.
Now to find out what ys is, we look at the right hand side of its definition,
ys ++ [1,2,3]
, good, so we have a concatenation of someList with [1,2,3], the first part of
ys is then someList. To determine ys, we must therefore first determine
someList. So, what is someList? someList = ys, so to determine the first part
of ys, we must find the whole of ys first -- oops, infinite recursion.
>
> > And from the rewriting, we can read off another representation of
> > cycle a fold.
> > We have, for all lists ks, ms:
> > ks ++ ms = foldr (:) ms ks
> >
> > So we can write variant 1 as the snappy
> >
> > myCycle xs = let ys = foldr (:) ys xs in ys
>
> I can't understand that one. I'll have to write it out:
>
> definition of foldr so I can refer to it:
> foldr step zero (x:xs) = step x (foldr step zero xs)
>
> myCycle2 [1, 2] =>
> ys = foldr (:) ys [1, 2]
> ---------------
> Here's the left hand side of the foldr definition:
> foldr step zero (x:xs) =>match these parameters to the args in the call:
> foldr (:) ys [1, 2] =
>
> Now writing out what's on the right hand side of the equals sign in the
> foldr definition using the args from the line above:
> = (:) 1 (foldr (:) ys 2:[])
> = 1:(foldr (:) ys 2:[])
> Expand the term in the parentheses:
> = 1:( (:) 2 (foldr (:) ys []) )
> = 1:( 2:(foldr (:) ys []) )
> = 1:2:(foldr (:) ys [])
> = 1:2:(ys)
> = 1:2:ys
>
> But ys is defined to be:
>
> foldr (:) ys [1, 2]
Actually, the implementation shouldn't need to go back to that definition at
this stage, it should now have reduced the thunk to
ys = 1:2:ys
, hopefully even by constructing a true cyclic list, making the ys on the
right hand side a pointer to the front of the list.
>
> So substituting into the last line:
>
> = 1:2:(foldr (:) ys [1, 2])
> = 1:2:( (:) 1 (foldr (:) ys 2:[])
> = 1:2:(1:(foldr (:) ys 2:[])
> = 1:2:1:( (:) 2 (foldr (:) ys [])
> = 1:2:1:( 2:(foldr (:) ys [])
> = 1:2:1:2:(foldr (:) ys [])
> = 1:2:1:2:(ys)
> = 1:2:1:2:ys
>
> But ys is defined to be:
>
> foldr (:) ys [1, 2]
>
> Therefore, that process goes on and on ad infinitum. Pretty slick.
>
> I guess haskell thunks the whole infinite expression, therefore
> the let expression:
>
> let ys = ....
> in ys
>
> doesn't cause an infinite loop in the ys = ... line, which means
> the second line executes, which means ys is returned as the
> result of the function call myCycle2 [1,2]?
>
>
Yes, it's thunked. It works because we can now determine the start of ys
without knowing anything about ys (provided that xs is nonempty). The result
of myCycle2 [1,2] is the thunk that says how to evaluate it. We give a name
to the result to be able to reference it in the calculation.
------------------------------
Message: 5
Date: Tue, 17 Mar 2009 12:30:33 +0000 (UTC)
From: 7stud <[email protected]>
Subject: [Haskell-beginners] Re: folds again -- myCycle
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Daniel Fischer <daniel.is.fischer <at> web.de> writes:
>
>variant 2:
>foldr rightAdd [] ones
> ~> foldr rightAdd [] (1:ones)
> ~> rightAdd 1 (foldr rightAdd [] ones)
> ~> (foldr rightAdd [] ones) ++ xs
>
>and variant 2 [amounts] to:
>myCycle2 xs = let ys = ys ++ xs in ys
>
>Ah, well. I again underestimated how much experience one
>needs to see it immediately, sorry once more.
>The right hand side of myCycle2's definition (if we specialise
>xs to, say, [1,2,3])
Ok, I see now. Using this definition:
>myCycle2 xs = let ys = ys ++ xs in ys
Then calling:
myCycle2 [1, 2, 3]
You get:
let ys = ys ++ [1, 2, 3]
But what is the value of ys on the right hand side?
Well, ys is equal to ys ++ [1, 2, 3]. So substituting
the value ys ++ [1, 2, 3] for ys in the right hand side
of the last line gives:
ys = (ys ++ [1, 2, 3]) ++ [1, 2, 3]
and then you need to substitute the value for ys
again on the right hand side, and so on ad infinitum.
That's bad because as in the earlier foldr example
ys is an infinite expression on the front of the list, and
any operation on the list will cause haskell to try and evaluate
that infinite expression.
> > myCycle2 [1, 2] =>
> > ys = foldr (:) ys [1, 2]
> > ---------------
> > Here's the left hand side of the foldr definition:
> > foldr step zero (x:xs) =>match these parameters to the args in the call:
> > foldr (:) ys [1, 2] =
> >
> > Now writing out what's on the right hand side of the equals sign in the
> > foldr definition using the args from the line above:
> > = (:) 1 (foldr (:) ys 2:[])
> > = 1:(foldr (:) ys 2:[])
> > Expand the term in the parentheses:
> > = 1:( (:) 2 (foldr (:) ys []) )
> > = 1:( 2:(foldr (:) ys []) )
> > = 1:2:(foldr (:) ys [])
> > = 1:2:(ys)
> > = 1:2:ys
> >
> > But ys is defined to be:
> >
> > foldr (:) ys [1, 2]
>
> Actually, the implementation shouldn't need to go back to that definition at
> this stage, it should now have reduced the thunk to
> ys = 1:2:ys
>
I figured haskell thunked the expression earlier than my last expansion:
>= 1:2:(foldr (:) ys [1, 2])
>= 1:2:( (:) 1 (foldr (:) ys 2:[])
>= 1:2:(1:(foldr (:) ys 2:[])
>= 1:2:1:( (:) 2 (foldr (:) ys [])
>= 1:2:1:( 2:(foldr (:) ys [])
>= 1:2:1:2:(foldr (:) ys [])
>= 1:2:1:2:(ys)
>= 1:2:1:2:ys
but I wanted to keep expanding the expression to show that it was creating
an infinite cycle.
> , hopefully even by constructing a true cyclic list, making the ys on the
> right hand side a pointer to the front of the list.
> >
Ok.
> > I guess haskell thunks the whole infinite expression, therefore
> > the let expression:
> >
> > let ys = ....
> > in ys
> >
> > doesn't cause an infinite loop in the ys = ... line, which means
> > the second line executes, which means ys is returned as the
> > result of the function call myCycle2 [1,2]?
> >
> >
>
> Yes, it's thunked. It works because we can now determine the start of ys
> without knowing anything about ys (provided that xs is nonempty). The result
> of myCycle2 [1,2] is the thunk that says how to evaluate it. We give a name
> to the result to be able to reference it in the calculation.
>
Thanks again for the great explanations.
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 9, Issue 17
****************************************
