principleMinor
Functional approach to splitting list into sub lists
Viewed 0 times
intosubsplittinglistsfunctionallistapproach
Problem
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.
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.
\$[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 [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;]Solution
Haskell:
EDIT
Example:
And, it turns out that my function is wrong :)
Correct version:
import Data.List.HT -- or Data.List.Grouping
takeruns xs@(x:xss) = map (map fst) pss
where pss = segmentAfter (uncurry (>)) $ zip xs xssEDIT
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) xsCode Snippets
import Data.List.HT -- or Data.List.Grouping
takeruns xs@(x:xss) = map (map fst) pss
where pss = segmentAfter (uncurry (>)) $ zip xs xssxs = [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], []]takeruns xs = map (map snd) pss
where pss = segmentAfter (uncurry (>)) $ zip (minBound:xs) xsContext
StackExchange Code Review Q#40013, answer score: 4
Revisions (0)
No revisions yet.