Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

count is not tail recursive #221

Open
LiamPack opened this issue May 17, 2022 · 0 comments
Open

count is not tail recursive #221

LiamPack opened this issue May 17, 2022 · 0 comments

Comments

@LiamPack
Copy link

LiamPack commented May 17, 2022

I've run into problems with the count function, which lifts 'a parsers to be 'a list parsers, stack overflowing. This is because the current implementation uses a recursive build-up of lifting cons to parsers in a non-tail-recursive fashion:

let count n p =
  if n < 0 
  then fail "count: n < 0"
  else 
    let rec loop = function
      | 0 -> return []
      | n -> lift2 cons p (loop (n - 1))
    in
    loop n

A naiive fix that I have is the following, which changes the above count to be tail-recursive:

(* A tail-recursive implementation of "count" *)
let count_tr n p =
  if n < 0
  then fail "count: n < 0"
  else
    let rec loop acc =
      function
      | 0 -> acc
      | n -> loop (lift2 cons p acc) (n - 1)
    in
    loop (return []) n
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant