Code examples in F# for http://matt.might.net/articles/higher-order-list-operations/

HigherOrderListOperations.fsx

// helpers
let inc x = x + 1
let dec x = x - 1
let even x = x % 2 = 0

// adding and subtracting one
let rec add1 lst =
    if List.isEmpty lst then []
    else (List.head lst) + 1 :: add1 (List.tail lst)

add1 [1; 2; 3]

let rec sub1 lst =
    if List.isEmpty lst then []
    else (List.head lst) - 1 :: add1 (List.tail lst)

sub1 [1; 2; 3]

// using map
List.map inc [1; 2; 3]

List.map dec [1; 2; 3]

// abstracting into map
let rec map f lst =
    if List.isEmpty lst then []
    else f (List.head lst)::map f (List.tail lst)

map inc [1 .. 3]

// map with matching
let rec mapMatch f lst =
    match lst with
    | [] -> []
    | head::tail -> f head::mapMatch f tail

mapMatch dec [1 .. 3]

// mapping with comprehension
[for x in 1 .. 3 -> x + 1]

// filtering
let rec filter p lst =
    if List.isEmpty lst then []
    elif p (List.head lst) then List.head lst::filter p (List.tail lst)
    else filter p (List.tail lst)

filter even [1 .. 10]

// filter with matching
let rec filterMatch p lst = 
    match lst with
    | [] -> []
    | hd::tl when p hd -> hd::filterMatch p tl
    | hd::tl -> filterMatch p tl

filterMatch even [1 .. 10]

// comprehension
[for x in 1 .. 10 do if even x then yield x]

// folding
let rec foldr cons nil lst =
    if List.isEmpty lst then nil
    else cons (List.head lst) (foldr cons nil (List.tail lst))

foldr (+) 0 [1 .. 4]

// folding with tail recursion
let rec foldl cons nil lst =
    if List.isEmpty lst then nil
    else foldl cons (cons (List.head lst) nil) (List.tail lst)

foldl (+) 0 [1 .. 4]

// build in
List.fold (+) 0 [1 .. 4]

// reducing
let rec reduce op lst =
    match lst with 
    | [] -> failwith "No elements in list"
    | [x] -> x
    | x::tl -> op x (reduce op tl)

reduce (+) [1 .. 4]

// zipping
let rec zip lst1 lst2 =
    match lst1, lst2 with
    | [], [] -> []
    | hd1::tl1, hd2::tl2 -> (hd1, hd2)::zip tl1 tl2

zip [1 .. 3] ['a' .. 'c']

// unzipping
let rec unzip lst =
    match lst with
    | [] -> ([], [])
    | (x, y)::tl ->
        let (xs, ys) = unzip tl
        (x::xs, y::ys)

unzip [(1, 'a'); (2, 'b'); (3, 'c')]

// unzipping with continuation
let rec unzipk k lst =
    match lst with
    | [] -> k [] []
    | (x, y)::tl -> unzipk (fun xs ys -> k (x::xs) (y::ys)) tl
    
unzipk (fun xs ys -> xs) [(1, 'a'); (2, 'b'); (3, 'c')]

// partitioning
let rec partition p lst =
    match lst with
    | [] -> ([], [])
    | hd::tl -> 
        let (ins, outs) = partition p tl
        if p hd then (hd::ins, outs)
        else (ins, hd::outs)

partition even [1 .. 10]

//partitioning with continuation
let rec partitionk p k lst =
    match lst with
    | [] -> (k [] [])
    | hd::tl -> partitionk p (fun ins outs -> if p hd then k (hd::ins) outs else k ins (hd::outs)) tl

partitionk even (fun evens odds -> evens) [1 .. 10]