Tail recursive addition of Peano numbers in F# using accumulators

Question

At Uni we were given a challenge of creating a tail recursive addition of Peano numbers using an accumulator. We aren't allowed to use any library function or other functions that we have created, but we are allowed to 'hide' the accumulator in an auxiliary function

Here's the type

  type Peano =
  | O
  | S of Peano

I'm stuck at how to execute the accumulator as it has no operation on the type defined, i.e. the following is not possible

  let tailAdd p1 p2 =
    let rec aux p1 p2 acc =
      match p1, p2 with
        | O, _   -> acc
        | S v, b -> aux v b (acc + v)

  aux p1 p2 O

Help xD

Brian Berns · Answer 1 · 2021-05-18T20:10:28.990

2

I don't want to give away the answer, since this is a homework problem, but I'll give you a hint: In the case where p1 matches with S v, you know that v = p1 - 1. Therefore, p1 + p2 = v + (p2 + 1). So how do you write p2 + 1 in Peano numbers?

edited May 18 '21 at 20:10

answered May 18 '21 at 14:52

Brian Berns

15,499
2
30
40

Ah yes, thank you, I came to that realisation yesterday and finally figured it out – LVOL May 19 '21 at 07:13
Now that you've figured it out, I just wanted to mention that this problem doesn't actually require an accumulator, so I'm not sure why it was assigned with that requirement. There's a simpler solution using the same basic idea. – Brian Berns May 19 '21 at 12:49

score 0 · Answer 2 · answered May 19 '21 at 07:12

0

Figured it out

let tailAdd p1 p2 = 
        let rec aux p1 p2 acc =
            match p1, p2 with
            | O, O   -> acc
            | a, S v -> aux v a (S (acc))
            | S v, b -> aux v b (S (acc))
        
        aux p1 p2 O

answered May 19 '21 at 07:12

LVOL

29
3

You can reduce duplication by combining the last two match cases. – phoog May 21 '21 at 03:09

Tail recursive addition of Peano numbers in F# using accumulators

2 Answers2