File: insertion.coma

package info (click to toggle)
why3 1.8.2-3
  • links: PTS, VCS
  • area: main
  • in suites: forky, sid
  • size: 45,028 kB
  • sloc: xml: 185,443; ml: 111,224; ansic: 3,998; sh: 2,578; makefile: 2,568; java: 865; python: 720; javascript: 290; lisp: 205; pascal: 173
file content (15 lines) | stat: -rw-r--r-- 402 bytes parent folder | download | duplicates (2) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
use int.Int
use list.List
use list.SortedInt
use list.Permut
use coma.Std
use coma.List

let rec insert (x: int) (l: list int) {sorted l}
               (return  (r: list int) {sorted r && permut r (Cons x l)})
= unList <int> {l}
    (fun (h: int) (t: list int) ->
      if {x < h} (-> return {Cons x l}) .
      insert {x} {t} . fun (r: list int) ->
      return {Cons h r})
    (return {Cons x Nil})