Haskell. (Maybe a) vs a

Question

belongs :: Eq(a) => a -> [a] -> Maybe a

belongs e (h:t) = if ( h == e) then Nothing else belongs e t
belongs e [] = Just e


nub :: Eq(a) => [a] -> [a]
nub l = nub' l [] 
    where 
        nub' [] new_list = new_list
        nub' (h:t) new_list = nub' t (new_list ++ [(belongs h new_list)])

Error:

Occurs check: cannot construct the infinite type: a0 = Maybe a0
Expected type: [a0]
  Actual type: [Maybe a0]
In the second argument of `belongs', namely `new_list'
In the expression: (belongs h new_list)
In the second argument of `(++)', namely `[(belongs h new_list)]'

I understand error. But I don't know how to repair it. I don't understand why Maybe Eq(a) cannot be matched with a. So how to repair it. I would like use Maybe here if is it possible.

you meant `new_list ++ Data.Maybe.maybeToList (belongs h new_list)`. — Will Ness, Mar 06 '16 at 18:00
Not wanting to sound pedantic, but the way you write type class constraints is quite unidiomatic and I am sure, disturbing for many. You can just drop the () around a type variable, there is nothing to parenthesize. — Ingo, Mar 06 '16 at 18:09

badcook · Accepted Answer · 2016-03-10T07:02:49.953

Imagine what would happen on that line if you instantiated a as a concrete type, e.g. Int. belongs would give you back a Maybe Int which you would wrap to make a [Maybe Int] and immediately try to concatenate it with new_list, which because you passed to belongs must be a [Int]. This is what the compiler is telling you; you are simultaneously trying to use one value as two different types.

To fix this you can match on the result of belongs before wrapping it in a list and appending it. If it's Just a append the a. If it's Nothing don't append anything. Side note: appending elements to the back of a list is very inefficient*. You might want to add everything to the front and then reverse at the end.

You have one other problem. Your definition of nub' simultaneously treats new_list as of type Maybe [a] (by returning a new_list in one case) and as of type [Maybe a] (if you fix the above). Edit: Not anymore after your edit.

* As @WillNess points out, this is a bit of a fiction. Because of the pervasive laziness of Haskell, most operations that are commonly said to be "expensive" are not expensive at creation time, but only when elements are being used. A lot of quadratic time slow-downs vs optimal linear time operations occur because an incorrect order of associating operations causes the retrieval of an element to incur linear time cost. His answer that he linked is a good explanation of this.

the matching and conditional appending that you describe can be nicely done with ``new_list ++ [a | Just a <- [belongs h new_list]]``. --- btw *appending* at the right is not inefficient; it's [the subsequent retrieval that's inefficient](http://stackoverflow.com/a/14942678/849891). Each element will be retrieved in O(n) time. — Will Ness, Mar 06 '16 at 18:09
Very good point. I was being lazy (pun not intended) and inaccurate. I'll edit my answer. — badcook, Mar 10 '16 at 06:26

score 2 · Answer 2 · answered Mar 07 '16 at 02:48

You have created a pair of functions; one claims to accept a list of any type ([a]) and return a list of the same type; the other takes a value of any type, a list of the same type, and returns a Maybe value of that same type.

A type and that type applied to Maybe are not the same type. But in the function that claims to be [a] -> [a], you are trying to combine [a] and [Maybe a] and get an [a] as a result. That's just not going to work.

In order to end up with the claimed [a] -> [a] signature, it will be necessary to remove the Maybe from the result of the call to belongs, which introduces it. You can do this in one of two ways: Either change belongs to no longer use Maybe, or do some sort of case-analysis on the Maybe to extract the underlying value and then wrap it in a list.

If you look at how the types for list and Maybe are defined, you may see a similarity:

data Maybe a = Nothing | Just a

data [a] = [] | a :: [a]

Both are sum types that have a case that represents absence of value! So you can simply replace Nothing in belongs with [] and Just e with [e]. Now the result can be directly concatenated with new_list in the second clause of nub'.

Alternatively, you can use belongs as it is, and take advantage of the correspondence between Maybe and the 1-element list to write a helper function that maps Nothing to [] and Just elem to [elem]. Or, as @Will Ness has pointed out, you could use the existing function from Data.Maybe called maybeToList that does exactly this.

Haskell. (Maybe a) vs a

2 Answers2