Using foldl on 2dimentional lists in Haskell

Question

I am trying to implement a function that collects all the values in an OrdTree in bfs order, and I also am having a hard time with this. Here is what I came with so far:

data OrdTree a = OrdTree a [OrdTree a]  deriving (Show)

bfsTree ::  OrdTree a ->  [a]
bfsTree tree = 
    let 
        use2DList level list (OrdTree a []) = (list!!level)++[a]
        use2DList currentLevel list (OrdTree a (branches)) =
            foldl 
                (\tree theList -> use2DList (currentLevel+1) theList tree) 
                ((list!!currentLevel)++[a]) 
                branches 
    in 
        concat (use2DList 0 [] tree)

and obviously I am stuck with bunch of errors I haven't managed to figure out.

1. I thought that since it's seemingly in scope, I should be able to use the currentLevel variable in foldl (specifically in the anonymous function), so am I? Is that okay? Or does it only have to work with the operands specified on the left of -> ?
2. I know that stuff is immutable, but list of lists.. if I append a value to one of the lists in a list it changes it, right? But what does such code return: (list!!position)++[value]?
3. Would this be better if I tried to curry it like this (if I got that right):
   foldl (use2DList (currentLevel+1)) (list!!currentLevel)++[a]) branches or is that even worse?

Sorry if it's too much text, I am just really confused with this stuff.

Answer 1

Is this what you mean by bfs order?

val (OrdTree a _) = a
children (OrdTree _ ts) = ts

bfs :: [OrdTree a] -> [a]
bfs ts = (map val ts) ++ bfs (concatMap children ts)

Note that I've written bfs to take a list of Ordtree a not just a single tree.

• The argument to bfs is the list of trees at the current level.
• map val ts are the values at the current level
• concatMap children ts are all of the trees at the next level

Update: Here is some of the analysis I did on your code.

First of all it doesn't compile, so I started to remove code until I the compiler stopped complaining, and I arrived at:

data OrdTree a = OrdTree a [OrdTree a]  deriving (Show)

bfsTree tree =
      let
          use2DList level list (OrdTree a []) = [a] ++ (list!!level)
      in concat (use2DList 0 [] tree)

Note there is no type signature on bfsTree - we are going to have ghc tell us what the signature is, and it responds with:

bfsTree :: OrdTree [a] -> [a]

This is clearly not right - we want OrdTree a -> [a]. The culprit, it turns out, is the concat, so apparently the code should read:

bfsTree tree =
      let
          use2DList level list (OrdTree a []) = [a] ++ (list!!level)
      in use2DList 0 [] tree

Now we can ask what the type signature of use2DList is, and ghc (really ghc-mod) responds with:

use2DList :: Int -> [[a]] -> OrdTree a -> [a]

Now we have to figure out what the foldl should be. foldl has the signature:

foldl :: (s -> t -> s) -> s -> [t] -> s

Clearly we are folding over the branches, i.e. t ~ OrdTree a, and the return type of use2DList is [a], so s ~ [a], so the first argument of foldl should look like:

(\listofa tree -> ...)

Since your function begins (\tree theList -> ...) it looks like you have to parameters swapped. And that's as far as I got.

The main suggestions are:

• use GHC and the type system to help you catch errors; add type signatures to all of your definitions - including helper functions
• learn to use the :t command in ghci to interrogate the inferred types of functions
• use the ghcmod-vim plugin for vim or the haskell-mode plugin for emacs so you can interrogate sub-expressions in your program