Runs the transformation function on all the nodes of your recursive data structure from the bottom up. Runs only once, hence the name!

transformOnce
    recurse
    simplifyNegate
    (Plus (Int_ 1) (Negate (Int_ 10)))
--> Plus (Int_ 1) (Int_ -10)

The recurse function tells the transform* functions which children to recurse to. In our example it looks like this:

recurse : (Expr -> Expr) -> Expr -> Expr
recurse fn expr =
    case expr of
        Int_ int ->
            Int_ int


        Negate e ->
            Negate (fn e)


        Plus left right ->
            Plus (fn left) (fn right)


        List_ es ->
            List_ (List.map fn es)

But you could of course make it skip some of the children by not applying the function on them.

WARNING: I'm not 100% sure but I think using this function with composed transformations (simplifyNegate >> simplifyPlus) that don't just shrink but also expand might not always lead to the fixpoint. To be sure, use transformAll and transformations combined with orList or a similar helper function.

An equivalent of Control.Lens.Plated.transform. (Hopefully.)

Runs the transformation function on all the nodes of your recursive data structure from the bottom up, stopping only when there's no more transformations applicable anywhere in the tree.

The transformation function has to return Nothing if there's nothing to be done. It's possible to create an infinite loop with a transformation that always returns Just!

transformAll
    recurse
    maybeSimplifyNegate
    (Plus (Int_ 1) (Negate (Int_ 10)))
--> Plus (Int_ 3) (Int_ -10)


transformAll
    recurse
    (orList_ [simplifyNegate, simplifyPlus])
    (Plus (Int_ 1) (Negate (Int_ 10)))
--> Int_ -7

An equivalent of Control.Lens.Plated.rewrite. (Hopefully.)

Gets all the children of the value.

Needs a function to tell it which children can be recursed to. Note this function is similar in function but different in type from the recurse function you'd give to transformOnce or transformAll.

This is how it could look:

recursiveChildren : (Expr -> List Expr) -> Expr -> List Expr
recursiveChildren fn expr =
    case expr of
        Int_ int ->
            []


        Negate e ->
            fn e


        Plus left right ->
            fn left ++ fn right


        List_ es ->
            List.concatMap fn es


children
    recursiveChildren
    (Plus (Int_ 1) (Negate (Int_ 10)))
-->
    [ Plus (Int_ 1) (Int_ -10)
    , Int_ 1
    , Negate (Int_ 2)
    , Int_ 2
    ]

Maybe.Extra.or made to work with the type signatures transformAll expects.

The argument order (and thus, whether you use this function in a pipeline or not) doesn't matter because transformAll literally tries to run the given transformation as long as it changes stuff (ie. until the fixed point is reached).

The way the transformations are combined makes sure that Nothing is returned only if no transformation can be applied anymore.

simplifyNegateOrPlus : Expr -> Maybe Expr
simplifyNegateOrPlus =
    or
        maybeSimplifyNegate
        maybeSimplifyPlus

Conceptually, this is mplus of the Alternative instance for (a -> Maybe a).

A nicer way to combine transformations for transformAll.

As with transformAll, the argument order (and thus, whether you use this function in a pipeline or not) doesn't matter because transformAll literally tries to run the given transformation as long as it changes stuff (ie. until the fixed point is reached).

The way the transformations are combined makes sure that Nothing is returned only if no transformation can be applied anymore.

simplifyAll : Expr -> Maybe Expr
simplifyAll =
    orList
        [ maybeSimplifyDoubleNegate
        , maybeSimplifyNegate
        , maybeSimplifyPlus
        ]

Again, conceptually, this is the mplus of the Alternative instance for (a -> Maybe a), combined with a fold.

A variant of orList for non-Maybe transformations.

orList_ : List (a -> a) -> a -> Maybe a
orList_ fns =
    orList (List.map toMaybe fns)


simplifyAll : Expr -> Maybe Expr
simplifyAll =
    orList_
        [ simplifyDoubleNegate
        , simplifyNegate
        , simplifyPlus
        ]

Modifies the transformation to return Nothing if it doesn't change the value.

simplifyNegate : Expr -> Expr
simplifyNegate expr =
    case expr of
        Negate (Int_ int) ->
            Int_ (negate int)


        _ ->
            expr


maybeSimplifyNegate : Expr -> Maybe Expr
maybeSimplifyNegate =
    toMaybe simplifyNegate


simplifyNegate      (Int_ 42) --> Int_ 42
maybeSimplifyNegate (Int_ 42) --> Nothing


simplifyNegate      (Negate (Int_ 42)) --> Int_ -42
maybeSimplifyNegate (Negate (Int_ 42)) --> Just (Int_ -42)

Modifies the transformation to return the original input if it returns Nothing.

maybeSimplifyNegate : Expr -> Maybe Expr
maybeSimplifyNegate expr =
    case expr of
        Negate (Int_ int) ->
            Just (Int_ (negate int))


        _ ->
            Nothing


simplifyNegate : Expr -> Expr
simplifyNegate =
    fromMaybe maybeSimplifyNegate


maybeSimplifyNegate (Int_ 42) --> Nothing
simplifyNegate      (Int_ 42) --> Int_ 42


maybeSimplifyNegate (Negate (Int_ 42)) --> Just (Int_ -42)
simplifyNegate      (Negate (Int_ 42)) --> Int_ -42