3

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

Will Ness
  • 70,110
  • 9
  • 98
  • 181
eivour
  • 1,678
  • 12
  • 20

2 Answers2

5

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

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • A small demonstration https://gist.github.com/pedrofurla/ffc61559d7a4fba74d4c42c6da0c3832 I was going to add to an answer, but to be complete it would need to go through evaluating everything manual. It would tedious. – pedrofurla Oct 02 '21 at 17:47
  • @pedrofurla you show the expansion of `second [1,2,3,4]` there, not of `xs`. :) – Will Ness Oct 02 '21 at 17:48
  • Yes. It demonstrates why it doesn't terminate. Doesn't it? – pedrofurla Oct 02 '21 at 17:49
  • I don't know. I'd have to follow the expansion of `xs`. I'm writing it right now. :) – Will Ness Oct 02 '21 at 17:50
  • > The only way to avoid this is to put take 7 on top of it. Is there a way to count how many elements we have until "the end", i.e. `second` returns `[]`? – eivour Oct 02 '21 at 17:52
  • 3
    `take 7` is not the only choice. You could also define your own fixpoint operator that worked by repeated application and equality checking, e.g. `fixEq :: Eq a => (a -> a) -> (a -> a); fixEq f guess | guess' == guess = guess | otherwise = fixEq f guess' where guess' = f guess`. – Daniel Wagner Oct 02 '21 at 17:52
  • It just occurred to me. The ideal example is xs = [] ++ second xs. – pedrofurla Oct 02 '21 at 17:57
  • @DanielWagner I tried `fixEq $ ([1,2,3,4] ++) . second` bbut it wanted a Show instance for `[a] ->[a]`. how was I supposed to call it? – Will Ness Oct 02 '21 at 17:59
  • @DanielWagner Is there a linear time solution? – eivour Oct 02 '21 at 17:59
  • @eivour "how to count" the only way I can think of is to write our own Haskell interpreter that'd do that. of course it wouldn't be able to do that _always_, because of the halting problem, but perhaps sometimes. if it did succeed, that would break the requirement (I think it is) for Haskell to find _least_ fixed points; but we'd probably give this operation a different name, like Daniel did above. – Will Ness Oct 02 '21 at 18:00
  • 1
    @WillNess Call it with any (finite, fully-defined) list as `guess`, e.g. `fixEq (([1,2,3,4]++) . second) []`. – Daniel Wagner Oct 02 '21 at 18:02
  • @eivour Linear with respect to what? What is the input that's changing and whose size we can freely vary? If it is the `[1,2,3,4]` that you plan to vary, then you can get O(n\*log(n)^2) using [Brent's algorithm](https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algorithm) for cycle detection in the implementation of `fixEq`, or O(n\*log(n)) using an algorithm specialized to this problem rather than a generic fixpoint operator. I don't see an obvious way to build the O(n\*log(n))-big output in less than O(n\*log(n)) time. – Daniel Wagner Oct 02 '21 at 18:08
  • @DanielWagner I meant linear with the length N of input list, that is `[1,2,3,4]` in the above case. In the above `fixEq` implementation, I thought we would have to make O(log N) comparison of lists of length O(N), resulting in O(NlogN) total time complexity. – eivour Oct 02 '21 at 18:13
  • @DanielWagner Isn't the output length O(N)? That is, N + N/2 + N/4 + ... = 2N, approximately. – eivour Oct 02 '21 at 18:14
  • @eivour You're almost right; except I believe you are making O(log(n)) comparisons of lists of length O(n\*log(n)). – Daniel Wagner Oct 02 '21 at 18:14
  • 1
    @eivour Err... yes! My math is off in both of my last comments. Here is a corrected one: the current implementation is O(n\*log(n)). Brent's algorithm has the same asymptotic complexity (but is probably faster anyway). No generic fixpoint algorithm can do asymptotically better. A specialized algorithm (rather than generic one) can get you to O(n). – Daniel Wagner Oct 02 '21 at 18:17
  • @DanielWagner but now `fixEq (([1,2,3,4,5,6]++) . id) []` hangs. so your _very clever I don't know how you've come up with it_ thing only works for the "contracting" second functions. (of course that was the question...) – Will Ness Oct 02 '21 at 18:21
  • @WillNess I think "contracting" probably isn't the right property. For example, `fixEq (\x -> (x^2+4)/(2*x))` terminates every `Double` I could think to try and I'm not sure what "contracting" could possibly mean for `Double`. The right property seems somewhat hard to concisely describe, though. – Daniel Wagner Oct 02 '21 at 18:34
  • @DanielWagner I now get `fixEq (([1,2,3,4]++) . second) $ take n [41..] == [1,2,3,4,2,4,4,48]` for all `n >= 8` that I could test. it produces correct result for `n < 8`. so making the first guess becomes a conundrum in itself. "will `[]` always work? can we be sure?" – Will Ness Oct 02 '21 at 20:14
  • and for `(([1..16]++) . second)` it's `[41..72]`. so it starts at twice the length for some reason. – Will Ness Oct 02 '21 at 20:22
  • 1
    @WillNess Like `fix`, `fixEq` only promises to return *a* fixpoint, and not necessarily *the fixpoint you have in mind*. – Daniel Wagner Oct 02 '21 at 22:18
  • @DanielWagner good point indeed! BTW I've never realized before that we can get to _a_ fixpoint of a list-creating function by iterating it from a starting candidate, just as we can with the number-valued functions like `sin`. 8-) – Will Ness Oct 03 '21 at 07:17
  • @pedrofurla I've finally edited with the specific steps. turns out the culprit is `r = 4:second r` as the last "cons cell" of the list. – Will Ness Oct 04 '21 at 18:16
  • @WillNess :) That was my point! Lol https://stackoverflow.com/questions/69418700/why-doesnt-this-fixed-point-computation-stop/69418812?noredirect=1#comment122697555_69418812 – pedrofurla Oct 05 '21 at 02:23
  • @pedrofurla it's not the same though. `xs = [] ++ second xs = second xs` is not `xs = 4:second xs`. :) both don't work of course, but I wanted to see exactly and specifically what happens _here_. – Will Ness Oct 05 '21 at 02:59
  • Yeah, value-wise the are not the same. Morally they are somewhat equivalent. ⊥ – pedrofurla Oct 05 '21 at 04:29
4

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.

Noughtmare
  • 9,410
  • 1
  • 12
  • 38
  • `second` returns `[]` whenever there are less than two elements in the list, so repeated application of `second` eventually returns `[]`. – eivour Oct 02 '21 at 17:56
  • Not really , eg `xs = [] ++ second xs`. – pedrofurla Oct 02 '21 at 18:06
  • 3
    @eivour For the input to have less than two inputs, it must *already have* a `[]`, as even a singleton list `[x]` is actually `x:[]` behind the scenes. And that `[]` has to come from somewhere -- the argument "`second` produces `[]` because it sees a `[]` that came from `second`" leads to the question, "but why did a `[]` come from `second`"... an infinite regress. For the `[]` to come from somewhere in a finite argument, it has to come from something other than a recursive call to `second`. – Daniel Wagner Oct 02 '21 at 18:55
  • 1
    @eivour ...and to be explicit about it, while Haskell does infinite *values* just fine, it doesn't do infinite *arguments* at all (here I use "arguments" in the sense of my previous comment, not in the sense of "function arguments"). – Daniel Wagner Oct 02 '21 at 18:58
  • @DanielWagner turns out the culprit here is `r = 4:second r` as the last "cons cell". I've edited my answer with the specifics. :) – Will Ness Oct 04 '21 at 18:13
  • @eivour This recursive definition never calls `second` on a list with less than two elements. Eventually there are less than two "already computed" elements, but at that point it's not a list that concretely ends after less than two elements, but rather a list that ends in a thunk, and forcing that thunk never yields a constructor. You're not starting at the concrete list `[1, 2, 3, 4]` and expanding it in steps to `[1, 2, 3, 4, 2, 4]` and then `[1, 2, 3, 4, 2, 4, 4]`; you start with `1 : 2 : 3 : 4 : `, forcing that to `1 : 2 : 3 : 4 : 2 : 4 : `. There's never a `[]`. – Ben Oct 05 '21 at 04:31