CODEWITHSUNDEEP
haskell
Scott Myers
Scott Myers

Reputation: 202

Recursive Fixpoint function in Haskell

I'm trying to create a function that finds the fixpoint of a function f (the case in which x = f x) while maintaining a list of the values recursive calls. I'm having trouble with the part of appending the recursive call to the previous list. Here's my code so far -- Thanks!

fixpointL :: (Int -> Int) -> Int -> [Int]
fixpointL f x | x == (f x) = [x]
              | otherwise = [x ++ fixpointL f (f x)]

Upvotes: 1

Views: 255

Answers (2)

Robin Zigmond
Robin Zigmond

Reputation: 18249

You didn't share what exactly wasn't working - Haskell's (or rather GHC's) compile-time errors can sometimes look a little impenetrable, but are always full of information if you know how to interpret them. Here the errors are:

<interactive>:4:30: error:
    * Couldn't match expected type `[Int]' with actual type `Int'
    * In the first argument of `(++)', namely `x'
      In the expression: x ++ fixpointL f (f x)
      In the expression: [x ++ fixpointL f (f x)]

<interactive>:4:30: error:
    * Couldn't match expected type `Int' with actual type `[Int]'
    * In the expression: x ++ fixpointL f (f x)
      In the expression: [x ++ fixpointL f (f x)]
      In an equation for `fixpointL':
          fixpointL f x
            | x == (f x) = [x]
            | otherwise = [x ++ fixpointL f (f x)]

As you can see, there are two different errors to do with type mismatches - but they're in fact closely related. Both are quite clear as to exactly what was wrong.

In the first one, it's complaining that the x in x ++ fixpointL f (f x) was supposed to be a [Int] (list of Ints), but was in fact an Int. This makes sense - the x is the second argument given to the function, which the type signature proclaims to be an Int. But you're trying to apply the (++) operator to it, and this operator has type:

Prelude> :t (++)
(++) :: [a] -> [a] -> [a]
  • that is, it takes two lists (which can hold any element), and returns another list of the same type. An Int certainly isn't a list, so it's no wonder that GHC can't make sense of this.

As for the second error - it's telling you that the expression x ++ fixpointL f (f x) was expected to be an Int but is actually a list ([Int]). The latter is because it's essentially pretending that you'll fix the first error and make x into the [Int] it's expecting - then that expression x ++ fixpointL f (f x) will indeed be a list of Ints (that is, a [Int]). But you've enclosed it in square brackets:

[x ++ fixpointL f (f x)]

which means a list containing only one element, that element being x ++ fixpointL f (f x), which as I've just explained is currently assumed to be of type [Int]. But since this is the return value of your function, and you've declared the return type to be [Int], that means that the contents of the [...] must be zero or more values (in this case one) of type Int. So that explains the other type mismatch.

How can we fix them? It seems that you want to take the output of fixpointL f (f x) - which we're assuming to be a list of Ints (your type signature says it is, so this is what GHC has to assume), and append the starting value, x, to the front of it. The correct way to write this, assuming you want to use the (++) operator, is like this:

[x] ++ fixPointL f (f x)

this takes the singleton list containing only x, and the result of the recursive call, and puts them together in one list. This typechecks, compiles, and works as presumably intended:

Prelude> fixpointL (^2) 1
[1]
Prelude> fixpointL (*2) 1
[1,2,4,8,16,32,64,128,256,512,...]

(Obviously in that second example I killed it as soon as I could, the actual output before I could was much longer but you get the idea.)

One final way you could improve the function is to use the "cons" operator (:), whose purpose is to add an element to the start of the list, without needing to construct a singleton list first. Since Haskell's lists are simple linked lists where each element contains a pointer to the next, this is always an efficient operation (as opposed to appending items to the end, which takes time proportional to the length of the list). While the performance difference here is miniscule, it's still considered much more idiomatic. So here is the working, idiomatic, version:

fixpointL :: (Int -> Int) -> Int -> [Int]
fixpointL f x | x == (f x) = [x]
              | otherwise = x : fixpointL f (f x)

Upvotes: 5

elikoga
elikoga

Reputation: 164

Check the types:

x :: Int
fixpointL f (f x) :: [Int]
(++) :: [a] -> [a] -> [a]

x ++ fixpointL f (f x) :: ??????????

[????] :: ?????

The line should be x : fixpointL f (f x)

Keep in mind I haven't tested it yet, could you post a function you'd like to test?

Upvotes: 1

Related Questions