Recursion.Traverse

This module provides traversals for common data structures that contain recursive types.

Prefer to use the functions that accept a continuation when possible (sequence____Then or traverse____Then) as they will be more efficient than folding and then mapping after.

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

sequenceList : List r -> Rec r t (List t)

Traverse a list where the elements are recursive types.

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


mapRoseTree : (a -> b) -> RoseTree a -> RoseTree b
mapRoseTree f =
    runRecursion <|
        \(Node a nodes) ->
            sequenceList nodes
                |> map (Node (f a))

sequenceListThen : List r -> (List t -> Rec r t a) -> Rec r t a

Traverse a list where the elements are recursive types and then perform a recursive action on the result.

traverseList : (x -> Rec r t a) -> List x -> Rec r t (List a)

Traverse a list where the elements contain recursive types.

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


mapKeyedRoseTree : (a -> b) -> KeyedRoseTree a -> KeyedRoseTree b
mapKeyedRoseTree f =
    runRecursion <|
        \(Node a nodes) ->
            traverseList (\( s, tree ) -> recurseMap tree (Tuple.pair s)) nodes
                |> map (Node (f a))

traverseListThen : (x -> Rec r t a) -> List x -> (List a -> Rec r t b) -> Rec r t b

Traverse a list where the elements contain recursive types and then perform a recursive action on the result.

Dict

sequenceDict : Dict comparable r -> Rec r t (Dict comparable t)

Traverse a Dict where the values are recursive types.

type HashTrie a
    = Leaf a
    | Node (Dict Char (HashTrie a))


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


                Node dict ->
                    sequenceDict dict
                        |> map Node

sequenceDictThen : Dict comparable r -> (Dict comparable t -> Rec r t a) -> Rec r t a

Traverse a Dict where the values are recursive types and then perform a recursive action on the result.

traverseDict :

(comparable -> v -> Rec r t a)

-> Dict comparable v

-> Rec r t (Dict comparable a)

Traverse a Dict where the values contain recursive types.

traverseDictThen :

(comparable -> v -> Rec r t a)

-> Dict comparable v

-> (Dict comparable a -> Rec r t b)

-> Rec r t b

Traverse a Dict where the values contain recursive types and then perform a recursive action the result.

Array

sequenceArray : Array r -> Rec r t (Array t)

Traverse an Array where the values are recursive types.

sequenceArrayThen : Array r -> (Array t -> Rec r t a) -> Rec r t a

Traverse an Array where the values are recursive types and then perform a recursive action on the result.

traverseArray : (x -> Rec r t a) -> Array x -> Rec r t (Array a)

Traverse an Array where the values contain recursive types.

traverseArrayThen : (x -> Rec r t a) -> Array x -> (Array a -> Rec r t b) -> Rec r t b

Traverse an Array where the values contain recursive types and then perform a recursive action on the result.

Maybe

sequenceMaybe : Maybe r -> Rec r t (Maybe t)

Traverse a Maybe where the value might be a recursive type.

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


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

sequenceMaybeThen : Maybe r -> (Maybe t -> Rec r t a) -> Rec r t a

Traverse a Maybe where the value might be a recursive type and then perform a recursive action on the result.

traverseMaybe : (x -> Rec r t a) -> Maybe x -> Rec r t (Maybe a)

Traverse a Maybe where the value might contain a recursive 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 ) -> recurseMap sepList (Tuple.pair sep))
                |> map (SeparatedList (f a))

traverseMaybeThen : (x -> Rec r t a) -> Maybe x -> (Maybe a -> Rec r t b) -> Rec r t b

Traverse a Maybe where the value might contain a recursive type and then perform a recursive action on the result.

Result

sequenceResult : Result e r -> Rec r t (Result e t)

Traverse a Result where the success value might be a recursive type.

sequenceResultThen : Result e r -> (Result e t -> Rec r t a) -> Rec r t a

Traverse a Result where the success value might be a recursive type and then perform an action on the recursive result.

traverseResult : (v -> Rec r t a) -> Result e v -> Rec r t (Result e a)

Traverse a Result where the success value might contain a recursive type.

traverseResultThen : (v -> Rec r t a) -> Result e v -> (Result e a -> Rec r t b) -> Rec r t b

Traverse a Result where the success value might contain a recursive type and then perform an action on the recursive result.

micahhahn/elm-safe-recursion/2.2.0