[Haskell-beginners] Re: folds again -- myCycle

20 Mar 2009

      Daniel Fischer  writes:
...
Am Donnerstag, 19. März 2009 20:32 schrieb 7stud:
...
Will Ness  writes:
...
let ws = foldr (:) [1,2,3] ws
head ws = head (foldr (:) [1,2,3] ws)
= head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws))
because 'ws' is getting matched against (a:as) pattern in foldr
definition, so is immediately needed, causing INFINITE looping. BUT
I'm confused by your statement that ws is getting matched against the
(a:as) pattern in the foldr definition, and therefore it is immediately
evaluated.   I didn't think the let expression:
...
let ws = foldr (:) [1,2,3] ws
would cause infinite looping.
Note this is again the left recursive bad definition. As long as we don't want 
to know anything about ws, the definition
ws = foldr (:) [1,2,3] ws
sleeps peacefully.
Check...................................................
..............................................................
............................................................
.............................................................
...
...
Wouldn't it be the head pattern that is being matched, and therefore head
triggers the evaluation?
If we need to know about the structure of ws, for example if we query
head ws
the evaluation of ws is triggered. In the case of head, we want to know if ws 
matches the pattern (_:_), in which case head returns the head of ws, or not, 
in which case head throws an exception.
So the implementation tries to match ws with the pattern (_:_). To see if it 
matches, it must evaluate ws, first replacing ws by the right hand side of 
its definition, foldr (:) [1,2,3] ws. Doesn't yet say if ws matches (_:_), so 
the foldr must be evaluated.
.........................
.........................
.........................
.........................
.........................
foldr  _    zero  []  =  zero  (from def of foldr)
...
foldr (:) [1,2,3] [] ~> [1,2,3]   
foldr (:) [1,2,3] (y:ys) =   y  :  foldr  (:) [1,2,3] ys
                           =  (:) y (foldr  (:) [1,2,3] ys)
  foldr step  zero  (x:xs) = step x (foldr  step  zero  xs)
                  (from definition of foldr)
...........................
...........................
..........................
..........................
...
To know which equation to use, the implementation tries to match ws with [].
Unfortunately, there is no information about the structure of ws available 
yet. So ws is replaced by the right hand side of its definition to find out 
whether it matches [], leading to
head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws)).

...
Dang, to see whether the inner foldr returns an empty list or not
?? 

I think you meant to say something like, "to see whether ws is an empty
list and therefore foldr returns [1, 2, 3]:

  foldr (:) [1,2,3] ws
...
foldr (:) [1,2,3] [] = [1,2,3]
we need to know whether ws is empty or not."
...
so we must replace ws in the inner foldr 
with the right hand side of its definition...
...
...
head (x:xs) = x
         ^^^^^^ the pattern
head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws))
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Although, I'm not seeing a pattern match here:
the expression which is *trying*(?) to be matched against the pattern
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
....
...
...
...
...