4 people like it.

Insertion Sort on List

A continuation function takes the result when it is computed. Here is an implementation of sorting on List via insertion. 

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 

// An insert function
let insert x lst =
  let rec insertCont x cont = function
    | [] -> cont ([x])
    | h::t as l -> if x<=h then cont(x::l) 
                   else insertCont x (fun accLst -> cont(h::accLst)) t
  insertCont x (fun x -> x) lst

// Sorting via insertion
let insertionSort l =
  let rec insertionSortAcc acc = function
    | [] -> acc
    | h::t -> insertionSortAcc (insert h acc) t
  insertionSortAcc [] l

let lst = [24;33;17;-5;-16;0;1;4;-3;2;8;-19]

let res = insertionSort lst

(*Results*)
//val res : int list = [-19; -16; -5; -3; 0; 1; 2; 4; 8; 17; 24; 33]
val insert : x:'a -> lst:'a list -> 'a list (requires comparison)

Full name: Script.insert
val x : 'a (requires comparison)
val lst : 'a list (requires comparison)
val insertCont : ('b -> ('b list -> 'c) -> 'b list -> 'c) (requires comparison)
val x : 'b (requires comparison)
val cont : ('b list -> 'c) (requires comparison)
val h : 'b (requires comparison)
val t : 'b list (requires comparison)
val l : 'b list (requires comparison)
val accLst : 'b list (requires comparison)
val x : 'a list (requires comparison)
val insertionSort : l:'a list -> 'a list (requires comparison)

Full name: Script.insertionSort
val l : 'a list (requires comparison)
val insertionSortAcc : ('b list -> 'b list -> 'b list) (requires comparison)
val acc : 'b list (requires comparison)
val lst : int list

Full name: Script.lst
val res : int list

Full name: Script.res
Raw view Test code New version

More information

Link:http://fssnip.net/e9
Posted:12 years ago
Author:Joel Huang
Tags: insertionsort , continuation

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.