Haskell recursion ":" replaced by || why?

haskell, recursion

Solution

Key idea

Use `:` to build up a list answer, `||` or `&&` to build up a True/False answer, and `+` or `*` to build up a numerical answer. Think about what you're combining - it doesn't have to be `:` all the time.

Detail

I think you mean to ask why you can't write

contains xs (y:ys) = prefix xs (y:ys)  :  contains xs ys

`:` is for gluing an element to the front of a list, so it has type `a -> [a] -> [a]`. This means you put a single thing on the left and a list on the right. You often use that in writing recursive functions, for example, you could define

increase :: [Int] -> [Int]
increase [] = []
increase (x:xs) = x + 5 : increase xs

Here `x + 5` is an `Int` and `increase xs` is a `[Int]`.

Let's look at your function. Its type is `contains :: String -> String -> Bool` so it takes a String, then a String, then gives you a Bool. Straight after the `=` you get `prefix xs (y:ys)`. Now `prefix` has the same type: `prefix :: String -> String -> Bool`, so now we've given it `xs` and `(y:ys)` it's giving us a Bool.

At the end of the line we've got `contains xs ys` which is a Bool too, so if we put `:` between them we've got something a bit like

False : True

but we're not allowed to do that because `True` isn't a list. (Remember `(:) :: a -> [a] -> [a]`.) You can do `False:[True]` (which would be `[False,True]`, but that's not what you want anyway.

You need to check whether the `xs` is there - either at the front of `(y:ys)` or later on. The symbol for or is `||`. So the code says

`xs` is in `(y:ys)` if it's at the front of it (`prefix xs (y:ys)`) or it's somewhere in `ys` (`contains xs ys`).

With the `:` (put-in-front-of symbol) in it it would say

`xs` is in `(y:ys)` if it's at the front of it (`prefix xs (y:ys)`), put that answer in front of these answers - it's somewhere in `ys` (`contains xs ys`).

which doesn't make sense. That's why you need or (`||`) not in-front-of (`:`).

Problem

Original source