CODEWITHSUNDEEP
f#
Kiven Zamora
Kiven Zamora

Reputation: 3

Reversing Order of Linked List data type in f#

I have to reverse the order of a linked list that uses the following data type: 

type IntList =
  | Nil
  | Cons of int * IntList

I have tried using a separate "append" method but I would like to know of a way to use a single function instead

let rec append num lst =
  match lst with
  | Nil -> Con (num,Nil)
  | Cons (hd,tl) -> L (hd ,append num tl)

let rec reverse lst = 
  match lst with 
  | Nil -> Nil
  | Cons (hd,tl) -> append hd (reverse tl)

Upvotes: 0

Views: 162

Answers (1)

3615
3615

Reputation: 3885

You can have it in one function, by using accumator variable. When you go recursivly to the end of your list you just do nothing, but keep a variable that will store the result when you return from recursion back to the start of your list.

When you get to the end of your list you just return your acuumulator which was initally an empty list and then add all elements to it, while returning back.

Since you will have accumulator as your recursive function param, it's better to wrap it inside a function that will do nothing else but just supplying the initial value of accumulator.

type IntList =
  | Nil
  | Cons of int * IntList 


let reverse lst = 
  let rec reverseHelper lst acc =
      match lst with 
      | Nil -> acc
      | Cons (hd,tl) -> reverseHelper tl (Cons (hd, acc))
  reverseHelper lst Nil

Upvotes: 3

Related Questions