PointedList: a list with a focus element

PointedList.fs

/// A list with a focus element.
/// Inspired by https://stackoverflow.com/a/38970195/1259408
/// Based on https://github.com/jeffwheeler/pointedlist/blob/master/Data/List/PointedList.hs
type PointedList<'a> =
  private PointedList of
    LeftsRev  : 'a list
    * Focus   : 'a
    * Rights  : 'a list
  with

  // FS1125
  // make sure the generic parameters actually get referenced in the static member
  // https://github.com/dotnet/fsharp/issues/2014#issuecomment-269364456

  static member map f (PointedList (ls, x : 'a, rs)) =
    PointedList (List.map f ls, f x, List.map f rs)

  static member foldBack f (PointedList (ls, x : 'a, rs)) z =
    List.fold (flip f) (List.foldBack f (x :: rs) z) ls

  static member toList (l : PointedList<'a>) =
    PointedList.foldBack List.cons l []

  static member toSeq (l : PointedList<'a>) =
    PointedList.toList l |> List.toSeq

  // F#+ integration

  [<EditorBrowsable(EditorBrowsableState.Never)>]
  static member Map (x, f) = PointedList.map f x

  [<EditorBrowsable(EditorBrowsableState.Never)>]
  static member FoldBack (x, f, z) = PointedList.foldBack f x z

  [<EditorBrowsable(EditorBrowsableState.Never)>]
  static member ToList x = PointedList.toList x

module PointedList =

  type Direction = Before | After

  /// Gets the current focus element of the list.
  let focus (PointedList (_, x, _)) = x

  /// Create a 'PointedList' with a single element.
  let singleton x = PointedList ([], x, [])

  /// Create a PointedList with a focus element and a list to follow
  /// after it.
  let create x xs = PointedList ([], x, xs)

  /// Try create Some PointedList if the list has at least one element,
  /// otherwise None. The provided list's head will be the focus of the
  /// list, and the rest of list will follow after it.
  let ofList = function
    | [] -> None
    | x :: xs -> Some <| PointedList ([], x, xs)

  /// Try create Some PointedList if the list has at least one element,
  /// otherwise None. The provided list's last element will be the focus
  /// of the list, and the rest of the list will precede before it.
  let ofListEnd list =
    List.rev list
    |> function
    | [] -> None
    | x :: xs -> Some <| PointedList (xs, x, [])

  /// Replace the focus of the list, retaining the befores and afters.
  let replace x (PointedList (ls, _, rs)) =
    PointedList (ls, x, rs)


  /// Returns the first element for which the predicate returns true.
  let tryFind pred (PointedList (ls, x, rs)) =
    let rec merge = function
      | [], ys      -> ys
      | x :: xs, ys -> x :: merge (xs, ys)

    if pred x then Some x
    else merge (ls, rs) |> List.tryFind pred

  /// Possibly move the focus to the next element.
  let tryMove d l =
    match d, l with
    | Before, PointedList ([], _, _) -> None
    | Before, PointedList (l :: ls, x, rs) ->
      Some <| PointedList (ls, l, x :: rs)
    | After, PointedList (_, _, []) -> None
    | After, PointedList (ls, x, r :: rs) ->
      Some <| PointedList (x :: ls, r, rs)

  /// Create a 'PointedList' of variations of the provided 'PointedList', in
  /// which each element is focused, with the provided 'PointedList' as the
  /// focus of the sets.
  let positions x =
    let ls = x |> List.unfold (tryMove Before >> map (fun y -> y, y))
    let rs = x |> List.unfold (tryMove After  >> map (fun y -> y, y))
    PointedList (ls, x, rs)

  /// Move the focus to the specified element, if it is present.
  let moveTo x = positions >> tryFind (focus >> (=) x)

  /// Insert an element before/after the focus, then move the focus
  /// to the new element.
  let insert d y (PointedList (ls, x, rs)) =
    match d with
    | Before -> PointedList (ls, y, x :: rs)
    | After  -> PointedList (x :: ls, y, rs)

  /// Possibly remove the element at the focus, then move the element from
  /// before/after to the focus. If no element is before, focus on the element
  /// in the other before/after. If the deletion will cause the list to be empty,
  /// returns None.
  let tryRemove d l =
    match d, l with
    | Before, PointedList ([], _, []) -> None
    | Before, PointedList (l :: ls, _, rs) -> Some <| PointedList (ls, l, rs)
    | Before, PointedList ([], _, r :: rs) -> Some <| PointedList ([], r, rs)
    | After , PointedList ([], _, []) -> None
    | After , PointedList (ls, _, r :: rs) -> Some <| PointedList (ls, r, rs)
    | After , PointedList (l :: ls, _, []) -> Some <| PointedList (ls, l, [])

  /// Remove all elements in the list except the focus.
  let removeOthers (PointedList (_, x, _)) =
    PointedList ([], x, [])

  let length (list : PointedList<_>) =
    PointedList.foldBack (fun _ i -> i + 1) list 0

  let isEnd = function
    | PointedList (_, _, []) -> true
    | PointedList _          -> false

  let isStart = function
    | PointedList ([], _, _) -> true
    | PointedList _          -> false