/// 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)