Translating code from https://sebfisch.github.io/haskell-regexp/regexp-play.pdf

Parts.ml

open List

let bind (xs : 'a list) (f : 'a -> 'b list) : 'b list =
  concat (map f xs)

let rec parts : 'a list -> 'a list list list = function
  | []      -> [[]]
  | [c]     -> [[[c]]]
  | c :: cs ->
    bind (parts cs) (fun (p :: ps) ->
      [(c :: p) :: ps; [c]::p::ps])