# Functional approach to splitting list into sub lists

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;]

• "Consecutive" would mean two integers (a, b) such that b = a + 1. It doesn't change the essence of the problem, though. Jan 25 '14 at 2:00
• thx for the heads up Jan 25 '14 at 10:06

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;])


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

• 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. Jan 25 '14 at 8:45
• @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 Jan 25 '14 at 8:56
• 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/… Jan 25 '14 at 9:19
• leventov, perhaps you could explain your code a bit more? How does it do what it does? Jan 25 '14 at 19:23
• @SimonAndréForsberg see edit Jan 25 '14 at 19:40

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.

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]]