CODEWITHSUNDEEP
recursionf#algebraic-data-types
huffola
huffola

Reputation: 55

Understanding tail recursion with stated data types

So I understand recursion relatively well, however in F# with the ability to create your own sets of data types I am not comprehending how to write a function to reference that particular scenario. Thanks for any help

type 'element mylist = PEANUT | BUTTER of 'element * 'element mylist

let exampleList = BUTTER (1, BUTTER (2, BUTTER (3, PEANUT)))

Attempting to write a tail recursive function that reverses this list?

Here is how I would write it traditionally

let rec helper a b =
      match a with
        | [] -> b
        | h::t -> helper t (h::b)

    let rev L = helper L []

Now here is what I've been attempting:

let rec tailrevMylist a L =
      match a with
      | [] -> []
      | PEANUT::t -> tailrevMylist t (BUTTER::L)
 

    let revMylist L =
      tailrevMylist  L []

*** BEGIN UPDATES/CHANGES ***

let rec tailrevMylist a b =
      match a with
      | PEANUT -> b
      | h::t -> tailrevMylist BUTTER (a, b)
 

    let revMylist L =
      tailrevMylist  L []

Still getting incorrect types -- attempted to use CONS instead of h but cannot due it expecting a union. *** END UPDATES ***

however when I try and run revMylist exmapleList I get an error due to the function expecting a 'a mylist list but having type int mylist in my test. I need to get the function to expect an int mylist.

*** SOLUTION ***

let rec tailrevMyList a b  =
      match a with
        | PEANUT -> b
        | BUTTER (head, tail) -> (tailrevMyList tail (BUTTER (head, b)))
 

    let revMylist L = tailrevMyList L PEANUT

Upvotes: 1

Views: 90

Answers (1)

glennsl
glennsl

Reputation: 29106

The definition of a list is essentially:

type 'a list = [] | :: of 'a * 'a list

which you might notice looks very similar to your definition of mylist. The only difference is the use of [] in place of PEANUT and :: in place of BUTTER, with :: also being an infix operator.

You might also notice that this means you're mixing list and mylist constructors in ways that make very little sense. So instead of trying to fix your current implementation I'll just tell you how to mechanically translate your helper function to use mylist by applying a couple of very simple rules:

  1. Replace [] with PEANUT.
  2. Replace a :: b with BUTTER (a, b).

That's really all there is to it. So instead of just giving you the answer I'll leave it to you to derive it yourself using these rules. Good luck!

Upvotes: 5

Related Questions