Tree structure as an instance of Foldable

[vstastny]

I aware that this is probably not the best place to ask a question, but still let me to do. I am trying to rewrite some of the examples in http://learnyouahaskell.com/functors-applicative-functors-and-monoids. I have difficulties with making a tree an instance of Foldable, i.e. I have defined

type Tree<'a> =
    | Empty
    | Node of ('a * Tree<'a> * Tree<'a>)

type Tree with
    static member treeFold (f) (tree:Tree<_>) (z) =
        match tree with
        | Empty -> z
        | Node (x, left, right) ->
            let l = Tree<_>.treeFold f left z
            let r = Tree<_>.treeFold f right z
            let n = f x z
            let res = f (f l n) r
            res
    static member inline instance (_:Foldr, x:Tree<_>, _) = fun (f, z) -> Tree<_>.treeFold f x z

let testTree =
    let one = Node (1, Empty, Empty)
    let six = Node (6, Empty, Empty)
    let three = Node (3, one, six)
    let eight = Node (8, Empty, Empty)
    let ten = Node (10, Empty, Empty)
    let nine = Node (9, eight, ten)
    let five = Node (5, three, nine)
    five

let _11_r32 = foldr (+) 0 testTree
let _11_r33 = foldr (*) 1 testTree

That works. However, this does not

let _11_r33a = foldMap (fun x -> Any (x > 15)) testTree

Am I missing something or have I defined anything incorrectly? Thank you.

[gusty]

It seems you defined a restricted fold. Fold signature should be:

treeFold (f:'a -> 'b -> 'b) (tree:Tree<'a>) (z:'b) :'b =

but yours is:

treeFold (f:'a -> 'a -> 'a) (tree:Tree<'a>) (z:'a) :'a =

If you define it like this it works:

static member treeFold f tree z =
    let rec toList = function
        | Empty -> []
        | Node (x, left, right) -> (x :: (toList left )) @ (toList right)
    List.foldBack f (toList tree) z

[vstastny]

Confirm, this works. However, drawback is that the whole structure is first transformed into other structure (first gone through) and the new structure is then gone through again. Moreover, lists appending is not efficient. If I understand correctly that the tree needs to be converted into the structure which is already instance of Foldable type, then the issue is in efficiency of transformation.

[gusty]

No, don't get me wrong and sorry if wasn't clear enough. I agree it was not an efficient implementation, I was lazy, but no, you don't need to convert it to a list. Much better would be something like this:

static member treeFold f tree z =
    match tree with
    | Empty -> z
    | Node (x, left, right) -> Tree<_>.treeFold f right (Tree<_>.treeFold f left (f x z))

Anyway I just wanted to show you that you had a bug in your foldTree implementation where the type of the final result was restricted to be the same as the type contained on the Tree. Your problem has nothing to do with the project, you can implement your foldTree in any way, you can use whatever you want, loops, mutable states, there is no restriction with the implementation, but the fold function should actually do the work, the function you defined doesn't fold when f changes the original type. As an example this will fail with your foldTree definition:

Tree<_>.treeFold (fun x y -> string x + y) testTree ""

And this has nothing to do with FsControl, it will fail even before using the project.

[vstastny]

Yes, you are right. Misunderstanding on my side. Thank you for your help.