10
\$\begingroup\$

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;]
\$\endgroup\$
  • 1
    \$\begingroup\$ "Consecutive" would mean two integers (a, b) such that b = a + 1. It doesn't change the essence of the problem, though. \$\endgroup\$ – Martin Jambon Jan 25 '14 at 2:00
  • \$\begingroup\$ thx for the heads up \$\endgroup\$ – citykid Jan 25 '14 at 10:06
3
\$\begingroup\$

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;])
\$\endgroup\$
4
\$\begingroup\$

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

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.

\$\endgroup\$
4
\$\begingroup\$

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]]    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.