foldl : ((a, Zipper/Tree a) -> b -> b) -> b -> Tree a -> b

[z5h]

I need a fold implmenetation which iterates through each (parent, children) tuple in the tree.
Am I correct in saying that this needs to be implemented within the project (as opposed to via the exposed API)?

[z5h]

For now I'll use the following:

import Tree exposing (Tree)
import Tree.Zipper as Zipper exposing (Zipper)


generalFold : (a -> b -> b) -> b -> Maybe a -> (a -> Maybe a) -> b
generalFold f b maybeA maybeNext =
    case maybeA of
        Just a ->
            generalFold f (f a b) (maybeNext a) maybeNext

        Nothing ->
            b


fold : (Zipper a -> b -> b) -> b -> Zipper a -> b
fold f b zipper =
    generalFold f b (Just zipper) Zipper.forward

Please close this issue if this is a reasonable solution and you don't think a fold like this has a place in the API. Thanks.

[zwilias]

Yeah, that seems like a pretty nice solution!

I'm curious if you could give an example use-case for such a function? It would help me think about the API and perhaps alternative ways of tackling the issue. (i.e. whether this is a missing function in Tree or in Zipper, or whether there may be a way to achieve this with comonadic extend/duplicate functions for the zipper, or ...)

[z5h]

I happen to be using it to support turing a tree into a Dict (so long as nodes are comparable). I need to do THAT in order to encode my trees and diff them.

toDict : Tree comparable -> Dict comparable (List comparable)
toDict tree =
    let
        addNode zipper dict =
            Dict.insert
                (Zipper.label zipper)
                (zipper |> Zipper.children |> List.map Tree.label)
                dict
    in
    zipperFold addNode Dict.empty (Zipper.fromTree tree)


encodeStringTree : Tree String -> Value
encodeStringTree =
    toDict >> Encode.dict identity (Encode.list Encode.string)

diff2 : Tree comparable -> Tree comparable -> Tree (Diff.Change comparable)
diff2 tree0 tree1 =
    let
        t0Dict =
            toDict tree0

        t1Dict =
            toDict tree1

        nodeToNodeAndChildren node =
            let
                k =
                    DiffExtra.return_ node

                diffed =
                    Diff.diff
                        (Dict.get k t0Dict |> Maybe.withDefault [])
                        (Dict.get k t1Dict |> Maybe.withDefault [])
            in
            ( node, diffed )
    in
    Tree.unfold nodeToNodeAndChildren (Diff.NoChange (Tree.label tree1))

[zwilias]

Thanks, that's super helpful! I'm going to let that sink in a little.

I'm wondering whether a Tree.merge : { onlyLeft : a -> b, onlyRight : a -> b, both : a -> a -> b } -> Tree a -> Tree a -> Tree b would make sense, as a parallel to Dict.merge and a useful abstraction for combining different versions of a tree.

The zipper-fold is really growing on me, though I think - if I'm incorporating similar functionality - it makes more sense to do it as part of the Tree module, and indeed offer a ((a, List (Tree a)) -> b -> b) -> b -> Tree a -> b type fold(l|r) which is essentially constructor replacement. Good catch!