Skip to content

Instantly share code, notes, and snippets.

@akbashev
Created April 24, 2022 21:19
Show Gist options
  • Save akbashev/2a6954be3d93f4bfc9995a4516c94d0d to your computer and use it in GitHub Desktop.
Save akbashev/2a6954be3d93f4bfc9995a4516c94d0d to your computer and use it in GitHub Desktop.
Experimenting with functional data structures
enum Tree<A> {
indirect case node(A, left: Tree<A>, right: Tree<A>)
case empty
}
extension Tree {
static func singleton(_ a: A) -> Tree {
return .node(a, left: .empty, right: .empty)
}
}
extension Tree: Equatable where A: Comparable {
func insert(_ a: A) -> Tree {
switch self {
case .empty:
return Tree.singleton(a)
case let .node(b, left, right):
switch a {
case _ where a == b: return .node(b, left: left, right: right)
case _ where a < b: return .node(b, left: left.insert(a), right: right)
case _ where a > b: return .node(b, left: left, right: right.insert(a))
default: fatalError("Impossible")
}
}
}
func elem(_ a: A) -> Bool {
switch self {
case .empty: return false
case let .node(b, left, right):
switch a {
case _ where a == b: return true
case _ where a < b: return left.elem(a)
case _ where a > b: return right.elem(a)
default: fatalError("Impossible")
}
}
}
}
extension Tree: CustomStringConvertible where A: Comparable {
var description: String {
switch self {
case .empty:
return "Empty"
case let .node(a, left, right):
let appendLeft: String = left != .empty ? "\n" : ""
let appendRight: String = right != .empty ? "\n" : ""
return "Node \(a) \(appendLeft)\(left) \(appendRight)\(right)"
}
}
}
let nums = [8, 6, 4, 1, 7, 3, 5]
let numsTree = nums.reversed()
.reduce(into: Tree<Int>.empty) { partialResult, value in
partialResult = partialResult.insert(value)
}
print(numsTree)
numsTree.elem(8)
numsTree.elem(100)
numsTree.elem(1)
numsTree.elem(10)
enum List<A> {
indirect case cons(a: A, list: List<A>)
case empty
}
extension List: Equatable where A: Equatable {}
extension List {
func head() -> Optional<A> {
switch self {
case .empty: return .none
case let .cons(a, _): return a
}
}
func tail() -> List<A> {
switch self {
case .empty: return .empty
case let .cons(_, next): return next
}
}
func last() -> Optional<A> {
switch self {
case .empty: return .none
case let .cons(a, .empty): return a
case let .cons(_, l): return l.last()
}
}
func index(_ index: Int) -> Optional<A> {
func indexTail(i: Int, xs: List) -> List {
switch i {
case 0: return xs
default: return indexTail(i: i - 1, xs: xs.tail())
}
}
switch index {
case 0: return self.head()
default: return indexTail(i: index, xs: self).head()
}
}
func length() -> Int {
switch self {
case .empty: return 0
default: return 1 + self.tail().length()
}
}
func insert(_ a: A) -> List {
List.cons(a: a, list: self)
}
func append(_ a: A) -> List {
switch self {
case .empty: return .cons(a: a, list: .empty)
case let .cons(head, list): return list.append(a).insert(head)
}
}
func concat(_ list: List) -> List {
switch self {
case .empty: return list
case let .cons(a, .empty): return .cons(a: a, list: list)
case let .cons(a, l): return l.concat(list).insert(a)
}
}
func map(_ f: (A) -> A) -> List {
switch self {
case .empty: return .empty
case let .cons(a, .empty): return .cons(a: f(a), list: .empty)
case let .cons(a, l): return .cons(a: f(a), list: l.map(f))
}
}
}
extension List: CustomStringConvertible {
var description: String {
switch self {
case .empty:
return ""
case let .cons(a, list):
return "\(a) \(list)"
}
}
}
precedencegroup ListPrecedence {
associativity: left
}
infix operator +: ListPrecedence
func + <A>(a: A, list: List<A>) -> List<A> {
List<A>.cons(a: a, list: list)
}
infix operator ++: ListPrecedence
func ++ <A>(a: List<A>, b: List<A>) -> List<A> {
a.concat(b)
}
List<Int>.cons(a: 2, list: .empty)
List<Int>.empty.head()
let threeTwoList = List<Int>.cons(a: 3, list: .cons(a: 2, list: .empty))
let threeTwoWithInfix = 3 + (2 + .empty)
false + (true + .empty)
threeTwoList == threeTwoWithInfix
let totalList = (5 + (4 + threeTwoList))
totalList ++ totalList.append(1)
(3 + (2 + .empty)).head()
totalList.tail()
totalList.last()
totalList.index(2)
totalList.insert(6)
totalList.append(1)
totalList.length()
let mapList = totalList.map { $0 * 2 }
print(mapList)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment