Using recursion in haskell

Question

Hi all so I have this homework assignment in Haskell where we have to work with the Nat Data type which only gives Zero and Succ(n) for one. So one is Succ(Zero), two is Succ(Succ(Zero)) and so on. We are also supposed to add subtract multiply these data types recursively.

One of the problems look like this

--Add two natural numbers.
--
--   `>>> add one two`
--   Succ (Succ (Succ Zero))
--
--   `>>> add Zero one == one`
--   True
--
--   `>>> add two two == four`
--   True
--
--   `>>> add two three == add three two`
--   True
--

My problem is when I am doing recursion I have a base case, but as I call it it just returns the base case and doesn't particularly bubble back up.

Any help or explanation on how to recursion in Haskell with pattern matching would be appreciated

EDIT: The code I have is

add :: Nat -> Nat -> Nat
add Zero   Zero = Zero
add Zero   (Succ i) =  Succ(pred i)
add (Succ i) Zero = Succ(pred i)
add (Succ i) (Succ j) = Succ(add i j)

Where pred is another function

pred :: Nat -> Nat
pred Zero = Zero
pred (Succ Zero) = Zero
pred (Succ i) = Succ(pred i)

If it only ever gives you the result of the base case, that sounds like the non-base case just recurs without doing anything with the result, but you should really show your code, so we can tell for sure. — sepp2k
– sepp2k, Commented Jan 20, 2017 at 17:15

Dietrich Epp · Accepted Answer · 2017-01-20 17:51:20Z

Here's an analysis:

add :: Nat -> Nat -> Nat

-- 0 + 0 = 0, looks good
add Zero   Zero = Zero

-- 0 + (1 + i) = 1 + (i - 1), wait, what?  No.
add Zero   (Succ i) =  Succ(pred i)

-- (1 + i) + 0 = 1 + (i - 1), again, no.
add (Succ i) Zero = Succ(pred i)

-- (1 + i) + (1 + j) = 1 + (i + j), no.
add (Succ i) (Succ j) = Succ(add i j)

You can see that it's a bit more obvious what is wrong when you translate it back into ordinary algebra.

Hint: You don't need to call pred, and you don't need more than two cases.

Also note that this is weird formatting:

Succ(pred i)
Succ(Zero)

Haskell should look like this:

Succ (pred i)
Succ Zero

Collectives™ on Stack Overflow

Using recursion in haskell

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related