CODEWITHSUNDEEP
list-comprehensioncoq
Schonfinkel
Schonfinkel

Reputation: 809

Rewriting list comprehension in Coq

I have the following Haskell function that outputs all possible ways to split a list:

split :: [a] -> [([a], [a])]
split []     = [([], [])]
split (c:cs) = ([], c : cs) : [(c : s1, s2) | (s1, s2) <- split cs]

Some example inputs:

*Main> split [1]
[([],[1]),([1],[])]
*Main> split [1,2]
[([],[1,2]),([1],[2]),([1,2],[])]
*Main> split [1,2,3]
[([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])]

I'm trying to write the same function in Coq, given there's no pattern matching by default and I don't want to define a notation for it yet, so I've decided to write a recursive function instead:

Require Import Coq.Lists.List.
Import ListNotations.

Fixpoint split {X : Type} (l : list X) : list (list X * list X) :=
  match l with
    | [] => [([], [])]
    | c::cs =>
      let fix split' c cs :=
          match cs with
            | [] => []
            | s1::s2 => (c++[s1], s2) :: split' (c++[s1]) s2
          end
      in
      ([], c :: cs) :: ([c], cs) :: split' [c] cs
  end.

which produces the same results:

     = [([], [1]); ([1], [])]
     : list (list nat * list nat)
     = [([], [1; 2]); ([1], [2]); ([1; 2], [])]
     : list (list nat * list nat)
     = [([], [1; 2; 3]); ([1], [2; 3]); ([1; 2], [3]); ([1; 2; 3], [])]
     : list (list nat * list nat)

However it's too verbose, any hints on how to convert this to a more readable function using HOFs in Coq?

Upvotes: 2

Views: 174

Answers (1)

Li-yao Xia
Li-yao Xia

Reputation: 33519

the comprehension in the Haskell version is syntactic sugar for map (or more generally flat_map).

Fixpoint split {X : Type} (l : list X) : list (list X * list X) :=
  match l with
  | [] => [([], [])]
  | c::cs =>
      ([], c :: cs) :: map (fun '(s1, s2) => (c :: s1, s2)) (split cs)
  end.

Upvotes: 5

Related Questions