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