Recursion.Traverse

This module provides traversals for common data structures with the Rec type.

What is a traversal?

A traversal is a transformation over a structure that preserves the shape of the structure. In this module, the traversal functions allow us to convert from a structure containing recursive types into a recursive type containing the structure.

If you are trying to write a map function over a recursive data structure, a traversal is likely what you want.

List

traverseList : (x -> Rec a b c) -> List x -> Rec a b (List c)

Traverse a list of recursive data types.

type KeyedRoseTree a
    = Leaf a
    | Node (List ( String, KeyedRoseTree a ))


mapKeyedRoseTree : (a -> b) -> KeyedRoseTree a -> KeyedRoseTree b
mapKeyedRoseTree f =
    runRecursion <|
        \tree ->
            case tree of
                Leaf a ->
                    base <| Leaf (f a)


                Node nodes ->
                    nodes
                        |> traverseList
                            (\( key, node ) ->
                                recurse node |> map (Tuple.pair key)
                            )
                        |> map Node

sequenceList : List a -> Rec a b (List b)

A specialization of traverseList when each element of the list is directly recursive.

sequenceList = traverseList recurse

type RoseTree a
    = Leaf a
    | Node (List (RoseTree a))


mapRoseTree : (a -> b) -> RoseTree a -> RoseTree b
mapRoseTree f =
    runRecursion <|
        \tree ->
            case tree of
                Leaf a ->
                    base <| Leaf (f a)


                Node nodes ->
                    nodes
                        |> sequenceList
                        |> map Node

Dict

traverseDict : (v -> Rec a b c) -> Dict comparable v -> Rec a b (Dict comparable c)

Traverse over a Dict where the values contain an recursive type.

sequenceDict : Dict comparable v -> Rec v b (Dict comparable b)

Sequence a Dict where the values directly are recursive types.

sequenceDict = traverseDict recurse

Maybe

traverseMaybe : (x -> Rec a b c) -> Maybe x -> Rec a b (Maybe c)

Traverse a maybe containing a recursive data type.

type SeparatedList sep val
    = SeparatedList val (Maybe ( sep, SeparatedList sep val ))


mapSeparatedList : (a -> b) -> SeparatedList sep a -> SeparatedList sep b
mapSeparatedList f =
    runRecursion <|
        \(SeparatedList a maybeOthers) ->
            maybeOthers
                |> traverseMaybe (\( sep, sepList ) -> recurse sepList |> map (Tuple.pair sep))
                |> map (SeparatedList (f a))

sequenceMaybe : Maybe a -> Rec a b (Maybe b)

A specialization of traverseMaybe for when the Maybe type is directly recursive.

sequenceMaybe = traverseMaybe recurse

type NonEmpty a
    = NonEmpty a (Maybe (NonEmpty a))


mapNonEmpty : (a -> b) -> NonEmpty a -> NonEmpty b
mapNonEmpty f =
    runRecursion <|
        \(NonEmpty a maybe) ->
            maybe
                |> sequenceMaybe
                |> map (NonEmpty (f a))

Result

traverseResult :

(value -> Rec a b c)

-> Result error value

-> Rec a b (Result error c)

Traverse over a Result where the success value can contain a recursive type.

sequenceResult : Result error value -> Rec value b (Result error b)

Sequence a Result where the success value directly is a recursive type.

sequenceResult = traverseResult recurse

Array

traverseArray : (x -> Rec a b c) -> Array x -> Rec a b (Array c)

Traverse an array of recursive data types.

type KeyedRoseTree a
    = Leaf a
    | Node (Array ( String, KeyedRoseTree a ))


mapKeyedRoseTree : (a -> b) -> KeyedRoseTree a -> KeyedRoseTree b
mapKeyedRoseTree f =
    runRecursion <|
        \tree ->
            case tree of
                Leaf a ->
                    base <| Leaf (f a)


                Node nodes ->
                    nodes
                        |> traverseArray
                            (\( key, node ) ->
                                recurse node |> map (Tuple.pair key)
                            )
                        |> map Node

sequenceArray : Array a -> Rec a b (Array b)

A specialization of traverseArray when each element of the list is directly recursive.

sequenceArray = traverseArray recurse

type RoseTree a
    = Leaf a
    | Node (Array (RoseTree a))


mapRoseTree : (a -> b) -> RoseTree a -> RoseTree b
mapRoseTree f =
    runRecursion <|
        \tree ->
            case tree of
                Leaf a ->
                    base <| Leaf (f a)


                Node nodes ->
                    nodes
                        |> sequenceArray
                        |> map Node

micahhahn/elm-safe-recursion/1.0.1