0 people like it.
Like the snippet!

Nested list functions

Higher-order functions for working with nested lists that reimplement various useful List module functions, but work on nested lists, preserving the original nesting strucutre when possible.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69: 
70: 
71: 
72: 
73: 
74: 
75: 
76: 
77: 
78: 
79: 
80: 
81: 
82: 
83: 
84: 
85: 
86:

/// Skip first n elements of the given nested list, preserving the nesting structure
let rec skipNested n list = 
  match list with 
  | _ when n <= 0 -> list
  | []::xss -> skipNested n xss
  | [_]::xss -> skipNested (n-1) xss
  | (_::xs)::xss -> skipNested (n-1) (xs::xss)
  | [] -> failwith "skipNested: insufficient number of elements"

/// Take the first n elements, preserving the nesting structure
let rec takeNested n list = 
  let rec loop accg accr n list = 
    let addg g = match g with [] -> accr | _ -> (List.rev g)::accr
    match list with 
    | _ when n <= 0 -> List.rev (addg accg)
    | []::xss -> loop accg accr n xss
    | [x]::xss -> loop [] (addg (x::accg)) (n-1) xss
    | (x::xs)::xss -> loop (x::accg) accr (n-1) (xs::xss)
    | [] -> failwith "takeNested: insufficient number of elements"
  loop [] [] n list

/// Keep taking elements while 'f' holds, preserving the nesting structure
let rec takeWhileNested f list = 
  let rec loop accg accr list = 
    let addg g = match g with [] -> accr | _ -> (List.rev g)::accr
    match list with 
    | (x::_)::_ when not (f x) -> List.rev (addg accg)
    | [] -> List.rev (addg accg)
    | []::xss -> loop accg accr xss
    | [x]::xss -> loop [] (addg (x::accg)) xss
    | (x::xs)::xss -> loop (x::accg) accr (xs::xss)
  loop [] [] list

/// Truncate nested list to a given length, preserving the structure
let rec truncateNested n list = 
  let rec loop accg accr n list = 
    let addg g = match g with [] -> accr | _ -> (List.rev g)::accr
    match list with 
    | _ when n <= 0 -> List.rev (addg accg)
    | []::xss -> loop accg accr n xss
    | [x]::xss -> loop [] (addg (x::accg)) (n-1) xss
    | (x::xs)::xss -> loop (x::accg) accr (n-1) (xs::xss)
    | [] -> List.rev (addg accg)
  loop [] [] n list

/// Take a slice from start to finish, preserving the strucutre
let sliceNested start finish list = 
  list |> skipNested start |> takeNested (finish - start + 1)

let sharedPrefixNested l1 l2 = 
  let rec loop accg accr l1 l2 = 
    let addg g = match g with [] -> accr | _ -> (List.rev g)::accr
    match l1, l2 with 
    | []::xss, []::yss -> loop accg accr xss yss
    | [x]::xss, [y]::yss when x = y -> loop [] (addg (x::accg)) xss yss
    | (x::xs)::xss, (y::ys)::yss when x = y -> loop (x::accg) accr (xs::xss) (ys::yss)
    | _ -> List.rev (addg accg), (l1, l2)
  loop [] [] l1 l2

/// Collect all elements, adding newly generated items to nesting groups
let collectNested f list =
  let rec appendRev acc xs = 
    match xs with x::xs -> appendRev (x::acc) xs | [] -> acc
  let rec loop accg accr list = 
    let addg g = match g with [] -> accr | _ -> (List.rev g)::accr
    match list with 
    | [] -> List.rev (addg accg)
    | []::xss -> loop accg accr xss
    | [x]::xss -> loop [] (addg (appendRev accg (f x))) xss
    | (x::xs)::xss -> loop (appendRev accg (f x)) accr (xs::xss)
  loop [] [] list

/// Map for nested lists
let mapNested f l = List.map (List.map f) l

/// Fold for nested lists
let foldNested f st l = List.fold f st (List.concat l)

/// Add index to elements of a nested list
let indexedNested l = 
  [ let mutable n = -1
    for g in l -> [ for v in g do n <- n + 1; yield n, v ] ]

/// Reverse for nested lists
let revNested l = 
  List.rev (List.map List.rev l)

val skipNested : n:int -> list:'a list list -> 'a list list
Skip first n elements of the given nested list, preserving the nesting structure

val n : int

Multiple items
val list : 'a list list

--------------------
type 'T list = List<'T>

val xss : 'a list list

val xs : 'a list

val failwith : message:string -> 'T

val takeNested : n:int -> list:'a list list -> 'a list list
Take the first n elements, preserving the nesting structure

val loop : ('b list -> 'b list list -> int -> 'b list list -> 'b list list)

val accg : 'b list

val accr : 'b list list

Multiple items
val list : 'b list list

--------------------
type 'T list = List<'T>

val addg : ('b list -> 'b list list)

val g : 'b list

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
    interface IReadOnlyList<'T>
    interface IReadOnlyCollection<'T>
    interface IEnumerable
    interface IEnumerable<'T>
    member GetReverseIndex : rank:int * offset:int -> int
    member GetSlice : startIndex:int option * endIndex:int option -> 'T list
    static member Cons : head:'T * tail:'T list -> 'T list
    member Head : 'T
    member IsEmpty : bool
    member Item : index:int -> 'T with get
    ...

val rev : list:'T list -> 'T list

val xss : 'b list list

val x : 'b

val xs : 'b list

val takeWhileNested : f:('a -> bool) -> list:'a list list -> 'a list list
Keep taking elements while 'f' holds, preserving the nesting structure

val f : ('a -> bool)

val loop : ('a list -> 'a list list -> 'a list list -> 'a list list)

val accg : 'a list

val accr : 'a list list

val addg : ('a list -> 'a list list)

val g : 'a list

val x : 'a

val not : value:bool -> bool

val truncateNested : n:int -> list:'a list list -> 'a list list
Truncate nested list to a given length, preserving the structure

val sliceNested : start:int -> finish:int -> list:'a list list -> 'a list list
Take a slice from start to finish, preserving the strucutre

val start : int

val finish : int

val sharedPrefixNested : l1:'a list list -> l2:'a list list -> 'a list list * ('a list list * 'a list list) (requires equality)

val l1 : 'a list list (requires equality)

val l2 : 'a list list (requires equality)

val loop : ('b list -> 'b list list -> 'b list list -> 'b list list -> 'b list list * ('b list list * 'b list list)) (requires equality)

val accg : 'b list (requires equality)

val accr : 'b list list (requires equality)

val l1 : 'b list list (requires equality)

val l2 : 'b list list (requires equality)

val addg : ('b list -> 'b list list) (requires equality)

val g : 'b list (requires equality)

val xss : 'b list list (requires equality)

val yss : 'b list list (requires equality)

val x : 'b (requires equality)

val y : 'b (requires equality)

val xs : 'b list (requires equality)

val ys : 'b list (requires equality)

val collectNested : f:('a -> 'b list) -> list:'a list list -> 'b list list
Collect all elements, adding newly generated items to nesting groups

val f : ('a -> 'b list)

val appendRev : ('c list -> 'c list -> 'c list)

val acc : 'c list

val xs : 'c list

val x : 'c

val loop : ('b list -> 'b list list -> 'a list list -> 'b list list)

val mapNested : f:('a -> 'b) -> l:'a list list -> 'b list list
Map for nested lists

val f : ('a -> 'b)

val l : 'a list list

val map : mapping:('T -> 'U) -> list:'T list -> 'U list

val foldNested : f:('a -> 'b -> 'a) -> st:'a -> l:seq<'b list> -> 'a
Fold for nested lists

val f : ('a -> 'b -> 'a)

val st : 'a

val l : seq<'b list>

val fold : folder:('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

val concat : lists:seq<'T list> -> 'T list

val indexedNested : l:seq<#seq<'b>> -> (int * 'b) list list
Add index to elements of a nested list

val l : seq<#seq<'b>>

val mutable n : int

val g : #seq<'b>

val v : 'b

val revNested : l:'a list list -> 'a list list
Reverse for nested lists

Raw view Test code New version

More information

Link:	http://fssnip.net/8aF
Posted:	yesterday
Author:	Tomas Petricek
Tags:	lists