I'm starting to do my firsts steps in Haskell. I have worked with recursion problems in the past using Python. Just for practice purposes, I'm trying to write a function witch reverse a list:

reverse2 lst =  if length lst == 1
                then lst !! 0
                else (last lst) : (reverse2 (init lst))

I get the error:

SimpleFunctions.hs:9:22: error:
    • Occurs check: cannot construct the infinite type: a ~ [a]
    • In the expression: (last lst) : (reverse2 (init lst))
      In the expression:
        if length lst == 1 then
            lst !! 0
        else
            (last lst) : (reverse2 (init lst))
      In an equation for ‘reverse2’:
          reverse2 lst
            = if length lst == 1 then
                  lst !! 0
              else
                  (last lst) : (reverse2 (init lst))
    • Relevant bindings include
        lst :: [a] (bound at SimpleFunctions.hs:7:10)
        reverse2 :: [a] -> [a] (bound at SimpleFunctions.hs:7:1)
  |
9 |                 else (last lst) : (reverse2 (init lst))
  |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Failed, no modules loaded.

But if I change by

reverse2 lst =  if null lst
                then []
                else (last lst) : (reverse2 (init lst))

It works!

Why the first option is not correct?

CodePudding user response：

You work with lst !! 0 but this returns an element of the list, not a list itself. You thus should wrap the first item in the list, for example with:

reverse2 :: [a] -> [a]
reverse2 lst =  if length lst == 1
                then [lst !! 0]
                else (last lst) : (reverse2 (init lst))

The time complexity of this is however O(n²) since determining the length of the list, and obtaining the last item takes linear time, and we have to do this for all items.

Usually this problem is solved by making use of an accumulator: an extra parameter that stores the reversed list thus far and makes recursive calls with a slightly altered accumulator until we reach the end of the list.

In that case we thus implement reverse as:

reverse :: [a] -> [a]
reverse = go []
    where go rv [] = rv
          go rv (x:xs) = go (x:rv) xs

here rv is the thus far obtained reverse of the list. For each item in the list, we prepend the reverse list with that item. If the list is thus [1,4,2,5], then we will make recursive calls that look like:

reverse [1,4,2,5]
  → go [] [1,4,2,5]
  → go [1] [4,2,5]
  → go [4,1] [2,5]
  → go [2,4,1] [5]
  → go [5,2,4,1] []
  → [1,4,2,5]

CodePudding user response：

Let's write out a type for your function. A reverse function takes a list and returns a list. So something like

reverse2 :: [a] -> [a]

Now, let's look at the implementation.

reverse2 lst =  if length lst == 1
                then lst !! 0
                else (last lst) : (reverse2 (init lst))

Both arms of the if need to return a [a], because that's the expected type. The else branch is fine; it makes a recursive call, then prepends an element. The result we get is a list. Great! The then branch, on the other hand, is problematic. lst is a [a], and (!!) has type

(!!) :: [a] -> Int -> a

So lst !! 0 has type a, not [a]. To return a singleton list, we need to be explicit about it.

reverse2 lst =  if length lst == 1
                then [lst !! 0]
                else (last lst) : (reverse2 (init lst))

Of course, now this function will fail on the empty list, since taking last and init of the empty list will fail. So we need a case for the empty list.

reverse2 :: [a] -> [a]
reverse2 [] = []
reverse2 lst =  if length lst == 1
                then [lst !! 0]
                else (last lst) : (reverse2 (init lst))

And at this point your null solution is looking simpler.