0

What's an elegant way to write the classic take function in CameLIGO? take takes the first num elements of a list.

This is how I'm writing it currently, and it's ugly. Here, message is a type I defined:

let rcons((xs, x): message list * message): message list =
  x :: xs

let reverse (xs: message list): message list =
  List.fold rcons xs ([]: message list)

let takeReverse ((num, xs): nat * message list): message list =
  let accumulate ((taken, x): message list * message) =
    if List.length taken < num then
      x :: taken
    else
      taken
    in
  List.fold accumulate xs ([]: message list)

// This is such an ugly construction.
let take ((num, xs): nat * message list): message list =
  let reversed = takeReverse (num, xs) in
  reverse reversed

Basically, to write take I'm reversing the list twice. I could write it more succinctly if I had non-tail recursion, but alas that's not offered by LIGO.

Thanks!

1 Answer 1

2

Accumulating the results to a linked list, and reversing the result would be more concise (and efficient, because your implementation traverses the entire input list, while this only looks at the prefix):

let take (count: int) (input: message list): message list =
  let rec go (acc, n, xs: message list * int * message list): message list =
    if n <= 0
    then acc
    else match xs with
         | [] -> acc
         | y::ys -> go (y::acc, n-1, ys) in
  reverse (go (([]: message list), count, input))

It's essentially same as the recursive implementation, where the accumulator is the stack and the last reverse is unrolling the stack inside-out.

1
  • Thanks! This is indeed nicer, and it's also good to know I can destructure lists inside match clauses. Mar 5, 2021 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.