Functional approach to splitting list into sub lists

Question

Here is my functional approach to split a list into sub lists, each having non-decreasing numbers, so the input

\$[1; 2; 3; 2; 4; 1; 5;]\$

computes to

\$[[1; 2; 3]; [2; 4]; [1; 5]]\$

The code works, but I need a while to understand it. I would prefer a solution that is more clear. Is there a way to make this more elegant or readable? Everything is allowed, F# mutables as well. Or do I just get used more to functional code reading?

The subsets are called "run"s in the code below.

// returns a single run and the remainder of the input
let rec takerun input =
 match input with
 | [] -> [], []
 | [x] -> [x], []
 | x :: xr -> if x < xr.Head then 
 let run, remainder = takerun xr
 x :: run, remainder
 else [x], xr
// returns the list of all runs
let rec takeruns input =
 match takerun input with
 | run, [] -> [run]
 | run, rem -> run :: takeruns rem
let runs = takeruns [1; 2; 3; 2; 4; 1; 5;]
> val runs : int list list = [[1; 2; 3]; [2; 4]; [1; 5]]

Edit:

Considering the helpful feedback I ended up with this reusable code. And got more used to functional programming, comparing imperative alternatives I meanwhile find the pure functional approach more readable. This version is good readable, although not tail recursive. For the small lists I had to deal with, readability was preferred.

// enhance List module
module List = 
 // splits list xs into 2 lists, based on f(xn, xn+1)
 let rec Split f xs =
 match xs with
 | [] -> [], []
 | [x] -> [x], []
 | x1 :: x2 :: xr when f x1 x2 -> [x1], x2 :: xr // split on first f(xn, xn+1)
 | x :: xr -> let xs1, xs2 = Split f xr
 x :: xs1, xs2
// Now takruns becomes quite simple
let rec takeruns input =
 match List.Split (>) input with
 | run, [] -> [run]
 | run, rem -> run :: takeruns rem
let runs = takeruns [1; 2; 3; 2; 4; 1; 5;]

• Martin Jambon: "Consecutive" would mean two integers (a, b) such that b = a + 1. It doesn't change the essence of the problem, though.
• citykid: thx for the heads up

Answer 1

A version that uses List.foldBack and List.pairwise

let split lst =
 let folder (a, b) (cur, acc) = 
 match a with
 | _ when a < b -> a::cur, acc
 | _ -> [a], cur::acc
 let result = List.foldBack folder (List.pairwise lst) ([List.last lst], []) 
 (fst result)::(snd result)
printfn "%A" (split [1; 2; 3; 2; 2; 4; 1; 5;])

Answer 2

Haskell:

import Data.List.HT -- or Data.List.Grouping
takeruns xs@(x:xss) = map (map fst) pss
 where pss = segmentAfter (uncurry (>)) $ zip xs xss

EDIT
Example:

xs = [1, 2, 3, 2, 4, 1, 5]
xss = [2, 3, 2, 4, 1, 5]
zip xs xss = [(1, 2), (2, 3), (3, 2), (2, 4), (4, 1)]
uncurry (>) (1, 2) == 1 > 2 = False
segmentAfter ... = [
 [(1, 2) /* False */, (2, 3) /* False */, (3, 2) /* True */],
 [(2, 4) /* False */, (4, 1) /* True */],
 []
]
map (map fst) (segmentAfter ...) = [[1, 2, 3], [2, 4], []]

And, it turns out that my function is wrong :) Correct version:

takeruns xs = map (map snd) pss
 where pss = segmentAfter (uncurry (>)) $ zip (minBound:xs) xs

• ChrisWue: This is not exactly a helpful code review. At least you should try and explain the solution in haskell and in how far it could be applied to other functional language as well.
• leventov: @ChrisWue I really don't know what to add to my answer. TS asked for "more readable or elegant version" -- my amost one-liner is not very readable, but probably the shortest. Initially TS mentioned Haskell
• citykid: thx for the helpful input. i realize that plain f# simply lacks some reusable functional basics, like Haskell's segmentAfter which can be found at hackage.haskell.org/package/utility-ht-0.0.1/docs/src/…
• Simon Forsberg: leventov, perhaps you could explain your code a bit more? How does it do what it does?
• leventov: @SimonAndréForsberg see edit

Answer 3

Since there is only one solution using sequences and one in Haskell, I thought that I still might post my code:

let partition list =
 let rec aux =
 function
 | trg,acc,[] -> acc::trg
 | trg,a::acc,x::xs when x<a 
 -> aux ((a::acc)::trg,[x],xs)
 | trg,acc,x::xs -> aux (trg,x::acc,xs)
 aux ([],[],list)|> List.map (List.rev) |> List.rev

Of course, running through the list twice as in the last line is bad (performance wise), however this could be easily solved by a custom revMap function that reverses and maps at the same time.

Answer 4

Using List.foldBack

let insert e state = 
 match state with
 | cur::rest ->
 match cur with
 | h::_ when e < h -> (e::cur)::rest // add e to current list
 | _ -> [e]::state // start a new list 
 | _ -> [[e]]
List.foldBack insert [1;2;3;2;4;1;5;] []
val insert : e:'a -> state:'a list list -> 'a list list when 'a : comparison
val it : int list list = [[1; 2; 3]; [2; 4]; [1; 5]]