So as the title says I'm supposed to make a function that takes a list and returns the list without the duplicates, but I can't use list comprehensions, only high-order functions and lambdas.

I've found this code from another users question.

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

unique :: (Eq a) => [a] -> [a]
unique [] = []
unique (x:xs)
  | has xs x  = unique xs
  | otherwise = x : unique xs

I understand how it works, but I don't understand how I could do the same thing with high-order fuctions. I'm new to Haskell so any tips would be appreciated.

CodePudding user response：

but I can't use list comprehensions, only high-order functions and lambdas.

The good news is: you don't use list comprehensions.

You can work with foldr :: (a -> b -> b) -> b -> [a] -> b here. Here the first function takes an element of type a and the "result" of the function of the rest of the list (so here the unique list of elements of the remaining elements). Your function thus should check if the element already appears in that result. You thus can implement this with:

unique :: Eq a => [a] -> [a]
unique = foldr f []
    where f x xs
            | … = …
            | otherwise = …

where you still need to fill in the … parts. You can even generalize this to any Foldable:

unique :: (Eq a, Foldable f) => f a -> [a]
unique = foldr f []
    where f x xs
            | … = …
            | otherwise = …

CodePudding user response：

You have been suggested foldr in another answer. This works for your has function but not for unique. The refactoring to foldr can be systematised, as taught in Graham Hutton's paper "A tutorial on the universality and expressiveness of fold".

In essence g = fold f v if and only if it can be written in the form,

g [ ] = v
g (x : xs) = f x (g xs)

Let's see how this works for the function has. Note: I will flip the order of the arguments in has to make it simpler.

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

We need to figure out our g, v and f.

g - The function has isn't quite our function g since it the latter only takes a list as argument and has also takes an a. Rather g = has a.

v - That one is trivial, v = False

f - According to the above it should satisfy f x (g xs) = g (x : xs), that is,

f x (has a xs) 
  | x == a    = True
  | otherwise = has a xs 

here we generalise the argument has a xs to any y, resulting in

f x ys = 
  | x == a    = True
  | otherwise = ys 

or in its lambda form if you prefer,

f = \x ys ->
  | x == a    = True
  | otherwise = ys 

arriving at,

has a = foldr f False 
  where 
    f x ys =
      | x == a    = True
      | otherwise = ys

Now let's see why it does not work for unique.

unique :: (Eq a) => [a] -> [a]
unique [] = []
unique (x:xs)
  | has x xs  = unique xs
  | otherwise = x : unique xs

Again we need to figure out our g, v and f. The g is of course our unique function. The v = [], the base case. Finally from second equation for g it follows that f should satisfy f x (g xs) = g (x : xs).

f x (unique xs) = 
  | has x xs  = unique xs
  | otherwise = x : unique xs

again lets abstract over unique xs to get a definition for f,

f x ys = 
  | has x xs  = ys
  | otherwise = x : ys

That did not work out because of the xs that remains in the definition. Note that the property g (x : xs) = f x (g xs) is specifying that the recursion is performed by applying a lambda at each step that only acts on x and the result of g xs. It does not act on xs.

We can change the definition of unique to make it a foldr though. Your definition checks if x is in xs, i.e. in the unprocessed list of elements, and if it is it doesn't add it. We can do the opposite, and check for x in the processed list of elements to check if it has already been added.

unique2 :: (Eq a) => [a] -> [a]
unique2 [] = []
unique2 (x:xs)
  | has x zs  = zs
  | otherwise = x : zs
  where zs = unique2 xs

with this change we have that f should satisfy,

f x (unique2 xs) = 
  | has x zs  = zs
  | otherwise = x : zs
  where zs = unique2 xs

and abstracting over unique2 xs, we get,

f x ys = 
  | has x ys  = ys
  | otherwise = x : ys

thus,

unique2 = foldr f []
  where 
    f x ys =
    | has x ys  = ys
    | otherwise = x : ys