How do I apply a function to foldr?

Question

This is a relatively simple haskell question but I am having alot of trouble with. I'm trying to apply this function 'add' to convert a list of strings into a BST. (The add function simply inserts a term) My questions is how to define the fold so that it applies the add function to the [String] so that it essentially inserts each function one by one?

My initial thought was that the function i'll be applying to xs would be (add _ basetree) where _ would be each element of xs and base tree would be the tree with one element, x. Then foldr would just apply that function to each element of xs. I'm not sure what is wrong, but this is giving me an error.

*** Expression     : foldr1 (add x (add x Empty)) xs
*** Term           : add x (add x Empty)
*** Type           : BST
*** Does not match : [Char] -> [Char] -> [Char]

 

data BST = MakeNode BST String BST
           | Empty

add :: String -> BST -> BST

listToTree :: [String] -> BST
listToTree (x:xs) = foldr (add x (add x Empty)) xs -- Here***

If someone can help me out that'll be great. I spent like almost 3 hours trying to figure out this foldr already ..

Answer 1

The type of foldr is

(a -> b -> b) -> b -> [a] -> b,

i.e. it takes a function that takes a b, and a list of [a]'s, and returns a b. Now add here is

(String -> BST -> BST),

so it becomes

(String -> BST -> BST) -> BST -> [String] -> BST,

now, I can't compile it, as I don't have the add function, but I believe

listToTree (x:xs) = foldr add (add x (add x Empty)) xs

will do the trick. It's type signature is the same at least. Now this should add the start of the list twice, but maybe your Add function ignores duplicates? It would better if you could include it, so that we might investigate it further.

Answer 2

As Gabriel says in a comment, you are combining manual recursion (the pattern match (x:xs)) with foldr in quite an unusual way. Usually you want to use either manual recursion, or you use foldr in cases where the recursion follows the pattern "repeatedly apply a function to the elements of a list until you've exhausted the list".

I assume your add function looks something like this:

add :: String -> BST -> BST
add string Empty            = MakeNode Empty string Empty
add string (MakeNode l s r) =
    if string < s
        then MakeNode (add string l) s r
        else MakeNode l s (add string r)

With this out of the way, the function listToTree would normally be written in one of two ways. The first is using pattern matching and recursion:

listToTree []     = Empty
listToTree (x:xs) = add x (listToTree xs)

That is, either you have an empty list, in which case you return the empty tree, or you have a head followed by a tail, in which case you add the head of the list to the tree returned by the tail of the list.

The other approach is to write listToTree by folding over the list. This abstracts out the recursion for you, so that you can just write

listToTree = foldr add Empty

This works because foldr has the type

foldr :: (a -> b -> b) -> b -> [a] -> b

and add and Empty have the types

add   :: String -> BST -> BST
Empty :: BST

specialising the types a and b, you get

foldr :: (String -> BST -> BST) -> BST -> [String] -> BST

which means that

foldr add Empty :: [String] -> BST 

Which of these should you prefer? Perhaps the first one is easier for a beginner to read and understand. However, as you gain more experience with Haskell you will find the second version becomes easier to understand. It's also more concise, and the fact that it's written in terms of a fold allows list fusion rules to be triggered more frequently, which may result in more efficient code.

Understanding foldr

The key to understanding folds, in my opinion, is to realize that a fold replaces list constructors with whatever functions and constants you give it. In Haskell there are two possible constructors for a list:

[]  :: [a]
(:) :: a -> [a] -> [a]

When you desugar all the syntax, lists actually look like this (this is valid Haskell - try it out!)

xs = 1 : 2 : 3 : []

When you call foldr op x0 xs, the fold effectively replaces all of the (:) constructors in xs with op, and all of the [] constructors with x0:

foldr op x0 xs = 1 `op` 2 `op` 3 `op` x0

Of course, there's an ambiguity here, because we don't know whether op associates to the left or to the right. In order for the types to work out, you must provide a function that associates to the right (that's why it's called a right fold), like this:

foldr op x0 xs = 1 `op` (2 `op (3 `op` x0))

A left fold is the same, except that it associates to the left instead (and puts the initial value at the start of the list rather than the end) so you end up with

foldl op x0 xs = ((x0 `op` 1) `op` 2) `op` 3

Answer 3

It looks like you want:

listToTree = foldr add Empty

foldr has type (a -> b -> b) -> b -> a

so it takes and accumulator function and an initial value. Empty is your initial tree value, and add constructs a new tree given an element and the existing tree.