Why doesn't this fixed-point computation stop?

user_3423503 0
Viewed 115

I am new to Haskell, and I have the following code:

second (x:y:xs) = y : second xs  -- returns every second element of a list
second _ = []

xs = [1,2,3,4] ++ second xs

I expect xs to be evaluated to [1,2,3,4,2,4,4], because that is the fixed point, i.e. [1,2,3,4,2,4,4] == [1,2,3,4] ++ second [1,2,3,4,2,4,4].

However, when I try to evaluate xs in GHCi, I get

Prelude> xs
[1,2,3,4,2,4,4

but it doesn't stop computing.

Could anyone explain why this doesn't stop, and is there a simple way to make the computation stop and return [1,2,3,4,2,4,4]?

infinite-recursion fixpoint-combinators infinite-loop lazy-evaluation haskell
2 Answers

[1,2,3,4,2,4,4] ++ [] is a fixed point of ([1,2,3,4] ++) . second, but it is not the least fixed point.

That is [1,2,3,4,2,4,4] ++ undefined, which is smaller. It is smaller in the sense that it is less defined than the first one.

The first one is more defined in that it has its 7th tail defined whereas the second's 7th tail is undefined.

That's the general outlook. But specifically we can follow the computations step by step, naming all the interim values and expanding the definition, and we will find out that the "get" point on the result catches up with the "put" point which is initially farther ahead, but the "get" point is twice faster than "put". So that when they meet there's nothing there yet that we've put there which we could get.

Thus the computation gets stuck, waiting for something to appear where there's nothing, and there's nothing that could put anything there.

The only way to avoid this is to put take 7 on top of it.

On an unrelated note I'd call that function seconds, not second.

So it goes like this:

xs = [1,2,3,4] ++ second xs

              a b c         (_:a:p) = xs = [1,2,3,4]++second xs
              ↓ ↓ ↓         (_:b:q) = p  = [    3,4,2]++second p
   =  1 2 3 4 2 4 4         (_:c:r) = q  = [        2,4]++second q
        ↓   ↓   ↓   ↓                 r  = [            4]++second r
        a   b   c    
      ↑   ↑   ↑   ↑                  r = drop 2 q = second q = 
      xs  p   q   r                    = second (2:4:r) = 4:second r

head r is well defined, it is

r = drop 2 q = second q 
             = second (_:c:r) 
             = c:second r
head r = c = 4
tail r =

but then we need to find tail r. Is it a (:) data node? Is it []?

       = tail (c:second r)
       = second r               -- (1)
       = second (c:second r)
       = case (c:second r) of
           (x:y:z) -> y:second z
           []      -> []
       = case (second r) of     -- (2)
           (y:z) -> y:second z

and so to find out what second r ( (1) ) is, we need to find out what second r ( (2) ) is.

We're stuck.

user_8498910

Another more intuitive way to see it is that the [] (end of the list) has to come from somewhere. The second function will only return [] once it encounters a [] in the input, so you end up with a chicken and egg situation. In this case the [] is never produced and therefore the computation can never stop.

user_152075680
Related