Linked list partition function and reversed results

by

Here’s a continuation-based version. It’s tail-recursive and returns the list in the original order.

let partitionWhileCps c l =
  let rec aux f = function
    | h::t when c h -> aux (fun (acc, l) -> f ((h::acc), l)) t
    | l -> f ([], l)
  aux id l

Here are some benchmarks to go along with the discussion following Brian’s answer (and the accumulator version for reference):

let partitionWhileAcc c l =
  let rec aux acc = function
    | h::t when c h -> aux (h::acc) t
    | l -> (List.rev acc, l)
  aux [] l

let test = 
  let l = List.init 10000000 id
  (fun f ->
    let r = f ((>) 9999999) l
    printfn "%A" r)

test partitionWhileCps // Real: 00:00:06.912, CPU: 00:00:07.347, GC gen0: 78, gen1: 65, gen2: 1
test partitionWhileAcc // Real: 00:00:03.755, CPU: 00:00:03.790, GC gen0: 52, gen1: 50, gen2: 1

Cps averaged ~7s, Acc ~4s. In short, continuations buy you nothing for this exercise.

More Related Contents:

  1. How to cast an object to a list of generic type in F#
  2. Need to partition a list into lists based on breaks in ascending order of elements (Haskell)
  3. Splitting a list of items into two lists of odd and even indexed items
  4. How to recognize the meaning of a linked list function in c++ [closed]
  5. Sort a list of objects in Flutter (Dart) by property value
  6. Concatenating two lists – difference between ‘+=’ and extend()
  7. How to reverse a singly linked list using only two pointers?
  8. Algorithm to generate all possible permutations of a list?
  9. What’s the most Pythonic way to identify consecutive duplicates in a list?
  10. How to check if all of the following items are in a list?
  11. Convert a matrix to a list of column-vectors
  12. Best algorithm to test if a linked list has a cycle
  13. Subsets in Prolog
  14. Finding all combinations of well-formed brackets
  15. Java 8: sort list of objects by attribute without custom comparator
  16. Lazy lists in Prolog?
  17. How do I split or chunk a list into equal parts, with Dart?
  18. How to count number of element occurrences in a list in Prolog
  19. Intersection and union of 2 lists
  20. Sliding window maximum in O(n) time
  21. Python: create a pandas data frame from a list
  22. How to extend a Scala list to enable slicing not by explicit position but by given predicate/condition
  23. Difference between a Seq and a List in Scala
  24. How to generate the power-set of a given List?
  25. How can I read the contents of a file into a list in Lisp?
  26. Haskell Monad – How does Monad on list work?
  27. Iterate over pairs in a list (circular fashion) in Python
  28. How does one enable selections in SwiftUI’s List
  29. Cons element to list vs cons list to element in Scheme
  30. Find non-common elements in lists

Leave a Comment