CODEWITHSUNDEEP
haskelldata-structuresinorderfoldable
Омар Ларрондо
Омар Ларрондо

Reputation: 1

Implementing Foldable for an n-ary tree in Haskell with inorder traversal

I'm trying to implement the Foldable instance for an n-ary tree data structure in Haskell. I want to define foldr such that it traverses the tree in inorder. However, I'm having trouble getting it to work correctly.

Here's my code:

data TreeL a = NodeL a [TreeL a] deriving (Show, Eq)

instance Foldable TreeL where
  foldr f b (NodeL x []) = f x b
  foldr f b (NodeL x (t:ts)) = foldr f (foldr f b ts)

I have a test property prop_tree_foldable that checks if the fold is done correctly and in order. It generates a random tree and checks if the result of foldr (:) [] (fst <$> t) is a sorted list of numbers. However, my implementation is failing this test.

I've tried a few different approaches, but I can't seem to get the traversal order right. Can someone help me understand what I'm doing wrong and how to fix it?

Upvotes: -4

Views: 121

Answers (2)

jpmarinier
jpmarinier

Reputation: 4733

For binary trees, it is accepted that in-order traversal means a traversal in Left-Root-Right order.

However, for TreeL traversals, with an unspecified number of child subtrees, it is not clear what in-order could mean.

The reasonable choices of traversal seem to be:

  1. process the root value Before the child subtrees
  2. process the root value After the child subtrees

Let's call the folding functions for these two choices foldrB and foldrA respectively.

We can use the list version of foldr to write the code for both options:

$ ghci
GHCi, version 9.4.5: https://www.haskell.org/ghc/  :? for help
...
λ> data TreeL a = NodeL a [TreeL a]  deriving  (Show, Eq)
λ> 
λ> foldrA f acc0 (NodeL x ts) = f x  (foldr (\t acc -> foldrA f acc t) acc0 ts)
λ> 
λ> foldrB f acc0 (NodeL x ts) = foldr  (\t acc -> foldrB f acc t)   (f x acc0)  ts
λ>

It turns out that flattening the tree into a plain list, using the usual method of foldr (:) [], gives a more intuitive result when using foldrA:

λ> 
λ> instance Foldable TreeL  where  foldr = foldrA
λ> 
λ> lf0 = NodeL (10::Int) []
λ> lf1 = NodeL (11::Int) []
λ> lf2 = NodeL (12::Int) []
λ> tr1 = NodeL (21::Int) [lf0, lf1]
λ> tr2 = NodeL (42::Int) [tr1,lf2]
λ> 
λ> foldr (:) [] tr2
[42,21,10,11,12]
λ> 
λ> toListFromTreeL = foldrA (:) []
λ> :type toListFromTreeL
toListFromTreeL :: TreeL t1 -> [t1]
λ> 
λ> toListFromTreeL tr2
[42,21,10,11,12]
λ>

That being said, there is nothing in the above code that could possibly make an ordered list from a randomly generated tree. That's for a sorting not a folding operation. We might be missing an essential piece of information regarding your prop_tree_foldable property.

Addendum:

It is actually possible to have the Haskell system provide the Foldable instance for TreeL automatically, using appropriate language extensions. One can proceed like this:

$ ghci
GHCi, version 9.4.5: https://www.haskell.org/ghc/  :? for help
...
λ> 
λ> :set -XDeriveFoldable
λ> :set -XStandaloneDeriving 
λ> 
λ> data TreeL a = NodeL a [TreeL a]  deriving  (Show, Eq)
λ> 
λ> deriving instance Foldable TreeL
λ> 
... define tr2 as before ...
λ>
λ> foldr (:) [] tr2
[42,21,10,11,12]
λ>

So FWIW the behavior of the « default » Foldable instance appears to be in agreement with foldrA.

Upvotes: 1

Carl
Carl

Reputation: 27023

I'm uncertain what the correct solution is, as I don't know what "in-order" means for that data type.

But I can tell you for sure that you're only generating a list of elements in leaf nodes. You're not doing anything with x in the recursive case. In fact, you're also throwing out t, so you aren't even seeing all leaf nodes. There's no way your solution can be correct if you aren't using the entire argument.

For what it's worth, it's far easier to write foldr in terms of toList for this data type. I'd strongly recommend starting there.

Upvotes: 3

Related Questions