I am studying a past exam and I came across a question where I must write a function called setFunc to generate a set where I apply a function on each element in a list of tuples (which are a result of the Cartesian product operation)

So first, I implemented a helper function to take the union of sets:

ordUnion :: (Ord a) => [a] -> [a] -> [a]
ordUnion a      []     = a
ordUnion []     b      = b
ordUnion (x:xs) (y:ys) = case compare x y of
   LT -> x : ordUnion xs  (y:ys)
   EQ -> x : ordUnion xs     ys
   GT -> y : ordUnion (x:xs) ys

Then I tried to implement the main function:

setFunc :: Ord c => (a -> b -> c) -> [a] -> [b] -> [c]
setFunc x y = f x y
setFunc (x:xs) (y:ys) = (f x y) OrdUnion (setFunc f xt ys)

but there are several errors in setFunc. Any help on fixing setFunc would be appreciated.

CodePudding user response：

I must use ordUnion somehow and I am not permitted to use sort.

This sort of constraint is expected to appear within the body of the question.

A core part of the problem is that we want the output list to be sorted (from your example), but we are told nothing about possible order-preserving properties of the argument function. So we must accept that the f x y output values will be produced in some unpredictable random order.

For example, we expect this equality to hold:

setFunc (*) [-7,2] [-7,3] == [-21,-14,6,49]

that is, the maximal output value results from the two minimal input values.

Hence, we are somewhat coerced into solving the problem in 2 steps:

1. produce the f x y output values in whatever order
2. sort the list produced in step 1.

Let's call the step 1 function cartesianFunc. It is easy to write it in recursive fashion:

cartesianFunc :: Ord c => (a -> b -> c) -> [a] -> [b] -> [c]
cartesianFunc f   []   ys  =  []
cartesianFunc f (x:xs) ys  =  (map (f x) ys)      (cartesianFunc f xs ys)

Note that we have dropped the useless Ord constraints on types b and c.

Testing:

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
...
 λ> 
 λ> :load q13784671.hs
 [1 of 1] Compiling Main             ( q13784671.hs, interpreted )
 Ok, one module loaded.
 λ> 
 λ> cartesianFunc (*) [1,2,4] [1,3,9]
 [1,3,9,2,6,18,4,12,36]
 λ> 

Now for step 2:

We may not use the library sort function. But we have to use function ordUnion, which merges two ordered lists into a bigger ordered list.

Assuming we had yet another function, say splitHalf, which could split a list into two roughly equal parts, we could obtain our own sort function by:

1. splitting the input list
2. recursively sorting its two halves
3. combining our two sorted halves using the merging ordUnion function.

To split a list, we can use the well-know tortoise-hare algorithm where at each iteration, the first part advances by one step and the second part advances by two steps.

This gives this code:

ordUnion :: (Ord a) => [a] -> [a] -> [a]
ordUnion a      []     = a
ordUnion []     b      = b
ordUnion (x:xs) (y:ys) = case compare x y of
    LT -> x : ordUnion xs  (y:ys)
    EQ -> x : ordUnion xs     ys
    GT -> y : ordUnion (x:xs) ys


splitHalfTH :: [a] -> ([a],[a])
splitHalfTH xs = th xs xs
  where
    th (y:ys)  (_:_:zs)  =  let  (as,bs) = th ys zs  in  (y:as, bs)
    th ys _              =  ([],ys)


mySort :: (Ord a) => [a] -> [a]
mySort  []   =  []
mySort  [a]  =  [a]
mySort  xs   =  let  (as,bs) = splitHalfTH xs  in  ordUnion (mySort as) (mySort bs)

and finally we can come up with our setFunc function by combining mySort and cartesianFunc:

setFunc :: Ord c => (a -> b -> c) -> [a] -> [b] -> [c]
setFunc fn xs ys = mySort (cartesianFunc fn xs ys)

Testing:

 λ> 
 λ> cartesianFunc (*) [1,2,4] [1,3,9]
 [1,3,9,2,6,18,4,12,36]
 λ> 
 λ> mySort $ cartesianFunc (*) [1,2,4] [1,3,9]
 [1,2,3,4,6,9,12,18,36]
 λ> 
 λ> setFunc  (*) [1,2,4] [1,3,9]
 [1,2,3,4,6,9,12,18,36]
 λ>