[Haskell-beginners] defining 'init' in terms of 'foldr'

[Hein Hundal]

  I am trying to understand the differences between two 
different solutions to the problem of expressing init in 
terms of foldr.

  The two solutions are called heinInit and chaddiInit.  
The heinInit does not work on infinite lists.  The
chaddiaiInit function does work on infinite lists.


heinInit v = fromJust $ foldr f Nothing v
   where
      f a Nothing = Just []
      f a (Just v) = Just (a:v)


chaddaiInit v = fromJust $ foldr f Nothing v
   where
      f x xs = Just (case xs of Nothing -> []; Just ys -> x:ys)


Here is my guess at the "trace" of the chaddaiInit code.

1)
head (chaddaiInit [1..])
2)
head (fromJust $ foldr f Nothing [1..])
3)
head (fromJust $ f 1 (foldr f Nothing [2..]))
4)
head (fromJust $ Just (case (foldr f Nothing [2..]) of 
   Nothing -> []; Just ys -> 1:ys))
5)
head (case (foldr f Nothing [2..]) of Nothing -> []; 
   Just ys -> 1:ys)
6)
head (case (f 2 (foldr f Nothing [3..])) of Nothing -> []; 
   Just ys -> 1:ys)
7)
head (case (Just (case (foldr f Nothing [3..]) of Nothing -> []; 
   Just ys -> 2:ys)) of Nothing -> []; Just ys -> 1:ys)
8)
head (1:(case (foldr f Nothing [3..]) of Nothing -> []; 
   Just ys -> 2:ys))
9)
1


Here is my guess at the "trace" of the heinInit code.


myinit v = fromJust $ foldr f Nothing v
   where
      f a Nothing = Just []
      f a (Just v) = Just (a:v)
    

1)
head (heinInit [1..])
2)
head (fromJust $ foldr f Nothing [1..])
3)
head (fromJust $ f 1 (foldr f Nothing [2..])
4)
head (fromJust $ f 1 (f 2 (fold f Nothing [3..])
5)
head (fromJust $ f 1 (f 2 (f 3 (fold f Nothing [4..])

And it just keeps going.  Is this the right idea?  Are my
"traces" a reasonable estimate of how Haskell 
evaluates those expressions?


Cheers,
Hein