Extracting Coq to Haskell

Question

I'm experimenting with Coq's extraction mechanism to Haskell. I wrote a naive predicate for prime numbers in Coq, here it is:

(***********)
(* IMPORTS *)
(***********)
Require Import Coq.Arith.PeanoNat.

(************)
(* helper'' *)
(************)
Fixpoint helper' (p m n : nat) : bool :=
  match m,n with
  | 0,_ => false
  | 1,_ => false
  | _,0 => false
  | _,1 => false
  | S m',S n' => (orb ((mult m n) =? p) (helper' p m' n))
  end.

(**********)
(* helper *)
(**********)
Fixpoint helper (p m : nat) : bool :=
  match m with
  | 0 => false
  | S m' => (orb ((mult m m) =? p) (orb (helper' p m' m) (helper p m')))
  end.

(***********)
(* isPrime *)
(***********)
Fixpoint isPrime (p : nat) : bool :=
  match p with
  | 0 => false
  | 1 => false
  | S p' => (negb (helper p p'))
  end.

Compute (isPrime 220).

(*****************)
(* isPrimeHelper *)
(*****************)
Extraction Language Haskell.

(*****************)
(* isPrimeHelper *)
(*****************)
Extraction "/home/oren/GIT/CoqIt/Primes.hs" isPrime helper helper'.

And after extracting the Haskell code, I wrote a simple driver to test it. I ran into two issues:

1. Coq exported its own Bool instead of using Haskell's built in boolean type.
2. Coq also used its own nat, so I can't ask isPrime 6 and I have to use S (S (...)).

module Main( main ) where    
import Primes    
main = do
    if ((isPrime (
        Primes.S (
        Primes.S (
        Primes.S (
        Primes.S (
        Primes.S (
        Primes.S ( O ))))))))
        ==
        Primes.True)
    then
        print "Prime"
    else
        print "Non Prime"

Answer 1

Regarding your first point - try to add

Require Import ExtrHaskellBasic.

to your Coq source. It specifies that the extraction should use Haskell's prelude definitions for some basic types. Documentation can be found here. There is also a similar module for strings.

Answer 2

I'm posting a complete solution here to make this post self contained. Hope others can make use of it.

(***********)
(* IMPORTS *)
(***********)
Require Import Coq.Arith.PeanoNat.

(************)
(* helper'' *)
(************)
Fixpoint helper' (p m n : nat) : bool :=
  match m,n with
  | 0,_ => false
  | 1,_ => false
  | _,0 => false
  | _,1 => false
  | S m',S n' => (orb ((mult m n) =? p) (helper' p m' n))
  end.

(**********)
(* helper *)
(**********)
Fixpoint helper (p m : nat) : bool :=
  match m with
  | 0 => false
  | S m' => (orb ((mult m m) =? p) (orb (helper' p m' m) (helper p m')))
  end.

(***********)
(* isPrime *)
(***********)
Fixpoint isPrime (p : nat) : bool :=
  match p with
  | 0 => false
  | 1 => false
  | S p' => (negb (helper p p'))
  end.

Compute (isPrime 220).

(********************************)
(* Extraction Language: Haskell *)
(********************************)
Extraction Language Haskell.

(***************************)
(* Use Haskell basic types *)
(***************************)
Require Import ExtrHaskellBasic.

(****************************************)
(* Use Haskell support for Nat handling *)
(****************************************)
Require Import ExtrHaskellNatNum.
Extract Inductive Datatypes.nat => "Prelude.Integer" ["0" "succ"]
"(\fO fS n -> if n Prelude.== 0 then fO () else fS (n Prelude.- 1))".

(***************************)
(* Extract to Haskell file *)
(***************************)
Extraction "/home/oren/GIT/CoqIt/Primes.hs" isPrime helper helper'.  

And here is the driver:

module Main( main ) where

import Primes
import Prelude

main = do
    if ((isPrime 220) == True)
    then
        print "Prime"
    else
        print "Non Prime"

It's interesting to mention the huge time difference between Coq's slow Compute (isPrime 220) and Haskell's compiled (and optimized!) super fast version of (is Prime 220).