Haskell - Create Set (unique sorted list) - no recursion, no nub

Question

is it Possible to create a function that will create a set with an input of a list.

I just can't think of any way without using recursion.

I can use high order functions like fold, filter, map, zip. I just can't have recursion in my function.

Obviously I can't use nub.

I've been banging my head trying to figure out how to get rid of duplicates without recursion or any type of loop (at least I don't think we can use loops, gonna ask).

Answer 1

One way to do it:

1. Sort the list.
2. Zip the list with its tail (turning e.g. [1,1,2,3] into [(1,1),(1,2),(2,3)])
3. Remove all the pairs where both items are the same.
4. Return the list containing the first element of the sorted list followed by the second item of each pair in the zipped list.

In code:

import Data.List

setify [] = []
setify xs = x : map snd (filter (uncurry (/=)) (zip sxs (tail sxs)))
    where sxs = sort xs
          x   = head sxs

Answer 2

Another would be to use a fold to accumulate the values along with a membership check if it has been seen before.

setify :: (Eq b) => [b] -> [b]
setify = foldl f []
where f acc next | next `elem` acc = acc 
                 | otherwise       = next:acc

Not the fastest method, but it get the job done.

Answer 3

Why all the complicated (and wrong!) solutions? Just do this:

uniq [] = []
uniq (x:xs)= x:(uniq (filter (/=x) xs))

setify xs = uniq $ sort xs -- If you want to sort too.

It filters each element from the tail of the list. Simple.