CODEWITHSUNDEEP
recursionf#
rwallace
rwallace

Reputation: 33649

Default recursion on recursive types

Idiomatic F# can nicely represent the classic recursive expression data structure:

type Expression = 
    | Number of int
    | Add of Expression * Expression
    | Multiply of Expression * Expression
    | Variable of string

together with recursive functions thereon:

let rec simplify_add (exp: Expression): Expression = 
    match exp with
    | Add (x, Number 0) -> x
    | Add (Number 0, x) -> x
    | _ -> exp

... oops, that doesn't work as written; simplify_add needs to recur into subexpressions. In this toy example that's easy enough to do, only a couple of extra lines of code, but in a real program there would be dozens of expression types; one would prefer to avoid adding dozens of lines of boilerplate to every function that operates on expressions.

Is there any way to express 'by default, recur on subexpressions'? Something like:

let rec simplify_add (exp: Expression): Expression = 
    match exp with
    | Add (x, Number 0) -> x
    | Add (Number 0, x) -> x
    | _ -> recur simplify_add exp

where recur might perhaps be some sort of higher-order function that uses reflection to look up the type definition or somesuch?

Upvotes: 4

Views: 87

Answers (1)

Tomas Petricek
Tomas Petricek

Reputation: 243096

Unfortunately, F# does not give you any recursive function for processing your data type "for free". You could probably generate one using reflection - this would be valid if you have a lot of recursive types, but it might not be worth it in normal situations.

There are various patterns that you can use to hide the repetition though. One that I find particularly nice is based on the ExprShape module from standard F# libraries. The idea is to define an active pattern that gives you a view of your type as either leaf (with no nested sub-expressions) or node (with a list of sub-expressions):

type ShapeInfo = Shape of Expression

// View expression as a node or leaf. The 'Shape' just stores
// the original expression to keep its original structure
let (|Leaf|Node|) e = 
  match e with
  | Number n -> Leaf(Shape e)
  | Add(e1, e2) -> Node(Shape e, [e1; e2])
  | Multiply(e1, e2) -> Node(Shape e, [e1; e2])
  | Variable s -> Leaf(Shape e)

// Reconstruct an expression from shape, using new list 
// of sub-expressions in the node case.
let FromLeaf(Shape e) = e
let FromNode(Shape e, args) = 
  match e, args with
  | Add(_, _), [e1; e2] -> Add(e1, e2)
  | Multiply(_, _), [e1; e2] -> Multiply(e1, e2)
  | _ -> failwith "Wrong format"

This is some boilerplate code that you'd have to write. But the nice thing is that we can now write the recursive simplifyAdd function using just your special cases and two additional patterns for leaf and node:

let rec simplifyAdd exp =
    match exp with
    // Special cases for this particular function
    | Add (x, Number 0) -> x
    | Add (Number 0, x) -> x
    // This now captures all other recursive/leaf cases
    | Node (n, exps) -> FromNode(n, List.map simplifyAdd exps)
    | Leaf _ -> exp

Upvotes: 4

Related Questions