Maintaining laziness: another example
Hello, While grading a Haskell student's work I ran into an example of a program not being lazy enough. Since it's such a basic and nice example I thought I'd share it with you: One part of the assignment was to define append :: [a] -> [a] -> [a], another to define cycle2 :: [a] -> [a]. This was her (the majority of the students in this course is female!) solution:
append :: [a] -> [a] -> [a] append [] ys = ys append xs [] = xs append (x:xs) ys = x : (append xs ys)
cycle2 :: [a] -> [a] cycle2 [] = error "empty list" cycle2 xs = append xs (cycle2 xs)
This definition of append works fine on any non-bottom input (empty, finite, infinite), but due to the unnecessary second append case, cycle2 never produces any result. Martijn.
Cool! Probably one should start teaching with 'case' instead of
pattern function definitions; that would put an accent on what is
forced and in what order. Only after the student understands the
laziness issues, introduce pattern signatures.
2009/6/8 Martijn van Steenbergen
Hello,
While grading a Haskell student's work I ran into an example of a program not being lazy enough. Since it's such a basic and nice example I thought I'd share it with you:
One part of the assignment was to define append :: [a] -> [a] -> [a], another to define cycle2 :: [a] -> [a]. This was her (the majority of the students in this course is female!) solution:
append :: [a] -> [a] -> [a] append [] ys = ys append xs [] = xs append (x:xs) ys = x : (append xs ys)
cycle2 :: [a] -> [a] cycle2 [] = error "empty list" cycle2 xs = append xs (cycle2 xs)
This definition of append works fine on any non-bottom input (empty, finite, infinite), but due to the unnecessary second append case, cycle2 never produces any result.
Martijn. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Eugene Kirpichov Web IR developer, market.yandex.ru
Hi, this is a very nice example. On 08.06.2009, at 14:31, Eugene Kirpichov wrote:
Cool! Probably one should start teaching with 'case' instead of pattern function definitions; that would put an accent on what is forced and in what order.
I like this idea.
Only after the student understands the laziness issues, introduce pattern signatures.
But I think this will not solve the problem. Even for an experienced Haskell programmer it is not easy to check whether a function is too strict. I think it would be helpful if you define your functions using case expressions but in general you do not want to do this. For example consider the implementation of insect of Data.List. intersect xs ys = [x | x <- xs, any (==x) ys] This definition is too strict. The evaluation of intersect [] [1..] yields [] while the evaluation of intersect [1..] [] does not terminate. This function can be improved such that it yields the empty list in both cases. This function was probably not implemented by a Haskell novice ; ) Cheers, Jan
Jan Christiansen wrote:
This definition is too strict. The evaluation of intersect [] [1..] yields [] while the evaluation of intersect [1..] [] does not terminate. This function can be improved such that it yields the empty list in both cases. This function was probably not implemented by a Haskell novice ; )
Right, so unlike in append in this example the extra case for [] is actually desirable! Welcome to Haskell. ;-) Martijn.
This might be slightly related. When I was assisting a Haskell lab course, I encountered solutions like the following:
removeRoot :: BSTree a -> BSTree a removeRoot (Node x Empty Empty) = Empty removeRoot (Node x left Empty) = left removeRoot (Node x Empty right) = right removeRoot (Node x left right) = undefined {- not needed for discussion -}
The first removeRoot case is unnecessary. Students new to Haskell (or
maybe new to recursion in general?) seem to consider more base cases
than needed.
-Raynor
On 6/8/09, Martijn van Steenbergen
Hello,
While grading a Haskell student's work I ran into an example of a program not being lazy enough. Since it's such a basic and nice example I thought I'd share it with you:
One part of the assignment was to define append :: [a] -> [a] -> [a], another to define cycle2 :: [a] -> [a]. This was her (the majority of the students in this course is female!) solution:
append :: [a] -> [a] -> [a] append [] ys = ys append xs [] = xs append (x:xs) ys = x : (append xs ys)
cycle2 :: [a] -> [a] cycle2 [] = error "empty list" cycle2 xs = append xs (cycle2 xs)
This definition of append works fine on any non-bottom input (empty, finite, infinite), but due to the unnecessary second append case, cycle2 never produces any result.
Martijn. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (4)
-
Eugene Kirpichov -
Jan Christiansen -
Martijn van Steenbergen -
Raynor Vliegendhart