ghci function multiple variable mentions in declarations not accepted

Question

I'm trying to learn Haskell, so I tried this:

$ ghci
GHCi, version 8.10.7: https://www.haskell.org/ghc/  :? for help
Prelude> :set +m
Prelude> let element :: (Eq a) => [a] -> a -> Bool   
Prelude|     element [] _ = False
Prelude|     element [x:_] x = True
Prelude|     element [_:xs] x = element xs x
Prelude| 

<interactive>:4:14: error:
    • Conflicting definitions for ‘x’
      Bound at: <interactive>:4:14
                <interactive>:4:19
    • In an equation for ‘element’
Prelude> 

So on line 4, why doesn't it just use the first binding, and force equivalence? This is obviously a toy problem; I know I can import list functions and use element = flip elem

My next attempt wil use guards...

Stackoverflow won't post this unless I include more "details" - let me know what details I'm missing and I'll add them in the comments.

Answer 1

x is not a variable; it's a pattern. Patterns have to be unique within a single definition so that it isn't ambiguous which value should be assigned to the name. The kind of unification you ask about is likely more complicated than it would be worth to avoid an explicit workaround.

If you want to check that the head of the first argument is equal to the second argument, use separate patterns and compare them explicitly in a guard or in the definition itself.

let element :: (Eq a) => [a] -> a -> Bool
    element [] _ = False
    element (x:xs) y | x == y = True
                     | otherwise = element xs y

Answer 2

Haskell does not work with unification, but with pattern matching. So mentioning a variable multiple times in the patterns does not unify these as is the case in Prolog, in fact they decided that patterns should be linear: don't mention the same variable twice in the same clause.

The pattern also looks like Prolog, since [x:_] actually, is not a list with x as head, it is a singleton list where for the single item, x matches with the first subelement, so [(x:_)]. You thus should work with (x:_) and (_:xs). You can use:

element :: Eq a => [a] -> a -> Bool   
element [] _ = False
element (x:xs) y = x == y || element xs y

To avoid passing the y variable in each recursive call, typically one works with a helper function and a where clause:

element :: Eq a => [a] -> a -> Bool
element zs y = go zs
  where go [] = False
        go (x:xs) = x == y || go xs