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]?

CodePudding user response：

[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.

CodePudding user response：

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.