Skip to content

Instantly share code, notes, and snippets.

@vbfox
Created March 8, 2015 13:16
Show Gist options
  • Save vbfox/431d74254011a4383e2d to your computer and use it in GitHub Desktop.
Save vbfox/431d74254011a4383e2d to your computer and use it in GitHub Desktop.
Small exercise of implementing a functional queue
module Queue
// "Purely Functional Data Structures" by Chris Okasaki, Page 18 (Figure 3.2)
open System
type queue<'a> = { F : 'a list; R : 'a list }
let empty = { queue.F = []; R = [] }
let isEmpty queue = List.isEmpty queue.F
let private makeQueue = function
| ([], r) -> { F = List.rev r; R = [] }
| (f, r) -> { F = f; R = r }
let snoc x { F = f; R = r } = makeQueue (f, (x::r))
let head = function
| { F = []; R = _} -> raise (new ArgumentException("The list is empty"))
| { F = x::_; R = _} -> x
let tail = function
| { F = []; R = _} -> raise (new ArgumentException("The list is empty"))
| { F = x::f; R = r} -> makeQueue (f, r)
let length { F = f; R = r } = (List.length f) + (List.length r)
let fromList lst = makeQueue (lst, [])
let toList { F = f; R = r } = List.append f (List.rev r)
let nth queue = queue |> toList |> List.nth
let private listReplaceAt index value list =
let rec listReplaceAtRec currentIndex remaining =
match remaining with
| h::t when currentIndex = index -> value :: (listReplaceAtRec (currentIndex + 1) t)
| h::t -> h :: (listReplaceAtRec (currentIndex + 1) t)
| [] -> []
listReplaceAtRec 0 list
let replaceAt index value queue = queue |> toList |> listReplaceAt index value |> fromList
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment