Created
March 8, 2015 13:16
-
-
Save vbfox/431d74254011a4383e2d to your computer and use it in GitHub Desktop.
Small exercise of implementing a functional queue
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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