CODEWITHSUNDEEP
haskell
K. Claesson
K. Claesson

Reputation: 659

The union of an arbitrary number of lists in Haskell

How can I get the union of an arbitrary number of lists in Haskell. For example, I would like a function that behaves like the one below:

example1 = union' [1,2,3] [1,4]
example2 = union' [1,2,3] [1,4] [2,6]
example1
[1,2,3,4]
example2
[1,2,3,4,6]

Upvotes: 0

Views: 1029

Answers (2)

typetetris
typetetris

Reputation: 4867

First a working code example:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}
module Main where
import Data.List (union)

class Unionable a t where
  union' :: [a] -> t

instance  Unionable a [a] where
  union' = id

instance  (Eq a, Unionable a t) => Unionable a ([a] -> t) where
  union' xs ys = union' (union xs ys)

main = do
  print $ (union' [1::Integer,2,3] [1::Integer,5,6] [1::Integer,7,3] :: [Integer])

mimiced from here.

You probably want to use such a function with literals and sadly, as you can see here, it will not be convienent to use it with polymorphic literals, as you will need to specify the type of every argument.

In other contexts, the types of the arguments have to be clear and the expected type of the result must be clear too, otherwise, you will need to add such type annotations.

For normal code it probably isn't worth the effort.

Let's explain what happens here, the compiler sees:

(union' [1::Integer,2,3] [1::Integer,5,6] [1::Integer,7,3] :: [Integer])

and it thinks, we need

union' :: [Integer] -> [Integer] -> [Integer] -> [Integer]

do we have such a union'? A candidate for that would be provided by the second instance declaration

a ~ Integer
t ~ [Integer] -> [Integer] -> [Integer]

but for that instance to be applicable, we need an instance of (Unionable a t) with those assignments. Do we have such an instance? Again the second instance declaration is a candidate, this time with

a ~ Integer
t ~ [Integer] -> [Integer]

but for that instance to be applicable, we need an instance of (Unionable a t) with those assignments. Do we have such an instance? Again the second instance declaration is a candidate, this time with

a ~ Integer
t ~ [Integer]

This time, we get such an instance from the first instance declaration with no additional constraints needed.

This means (ommitting the type annotations for clarity)

union' [1,2,3] [1,5,6] [1,7,3]
= unions' (union [1,2,3] [1,5,6]) [1,7,3]
= unions' (union (union [1,2,3] [1,5,6]) [1,7,3])
= id (union (union [1,2,3] [1,5,6]) [1,7,3])
= (union (union [1,2,3] [1,5,6]) [1,7,3])
= [1,2,3,5,6,7]

Upvotes: 2

chepner
chepner

Reputation: 531460

A function in Haskell only takes one argument. A "two"-argument function is really a function that returns another function that returns the ultimate return value. As such, there is no way for a function to take a variable number of arguments, because the return type of such a function wouldn't be well defined.

If you want to take the union of an arbitrary number of lists, your function should take a list of lists, since a list can contain an arbitrary number of elements.

union' :: Eq a => [[a]] -> [a]
union' = foldr unionOfTwo []
  where unionOfTwo :: Eq a => [a] -> [a] -> [a]
        unionOfTwo xs ys = ...  -- left as an exercise

where unionOfTwo knows how to compute the union of exactly two lists. Effectively, union' sets aside the first list in the input, recursively computes the union of the remaining inputs, then computes the union of that result and the original first list. Put another way,

union' []  = []
union' (xs:xss) = unionOfTwo xs (union' xss)

Upvotes: 3

Related Questions