List implementation in Swift
Functional data structure is slightly different from object oriented one. It have persistence and not mutated. I implement this data structure in Swift which have characteristic both object oriented and functional programming. The first example is list.
List declaration
List is declared using enum. nil means empty and cons means pair of value(type T) and list that concatenated to the end of itself. indirect is necessary to use itself recursive(cons(T, List<T>)).
enum List<T: Equatable> {
case `nil`
indirect case cons(T, List<T>)
}List must be able to check the equivalence. We can enable it by conforming List to Equatable protocol.
extension List: Equatable {
static func ==(lhs: List, rhs: List) -> Bool {
switch (lhs, rhs) {
case (.`nil`, .`nil`):
return true
case (.cons(let h, let t), .cons(let h1, let t1)):
return h == h1 && t == t1
default:
return false
}
}
}
let list = List<Int>.cons(1, .cons(2, .cons(3, .`nil`)))
let list1 = List<Int>.cons(1, .cons(2, .cons(3, .`nil`)))
let list2 = List<Int>.cons(1, .cons(2, .cons(3, .cons(4, .`nil`))))
list == list1 // true
list == list2 // falseConform to CustomStringConvertible protocol is useful to pretty print in the console.
extension List: CustomStringConvertible {
var description: String {
switch self {
case .`nil`:
return "nil"
case .cons(let head, let tail):
return "\(head),\(tail)"
}
}
}
let list = List<Int>.cons(1, .cons(2, .cons(3, .`nil`)))
print(list) //1,2,3,nilVariable
There is two point that pays to attention. First, All variable have the same format that use pattern match to extract associated values of cons. Second, length and last use recursion. Functional programming many time use these technics.
extension List {
var isEmpty: Bool {
switch self {
case .`nil`:
return true
case .cons:
return false
}
}
var head: T? {
switch self {
case .`nil`:
return nil
case .cons(let head, _):
return head
}
}
var tail: List<T>? {
switch self {
case .`nil`:
return nil
case .cons(_, let tail):
return tail
}
}
var length: Int {
switch self {
case .`nil`:
return 0
case .cons(_, let tail):
return 1 + tail.length
}
}
var last: T? {
switch self {
case .`nil`:
return nil
case .cons(let head, .`nil`):
return head
case .cons(_, let tail):
return tail.last
}
}
}
let list = List<Int>.cons(1, .cons(2, .cons(3, .`nil`)))
list.isEmpty // false
list.head // 1
list.tail // 2,3,nil
list.length // 3
list.last // 3Function
I implemented four basic functions. They used recursion and pattern match too. The Flow of their is close. Take add(value: T) as an example, it checks self and create new cons until it has head and tail. The tail of new cons call tail.add(value: value)and it repeat several time . Creating new cons each time called add(value: value) means create intermediate state as other instance. It able to persist the state of List. We can refer to initial state of List after called add(value: T).
extension List {
func add(value: T) -> List<T> {
switch self {
case .`nil`:
return List<T>.cons(value, .`nil`)
case .cons(let head, let tail):
return .cons(head, tail.add(value: value))
}
}
func remove(index: Int) -> List<T> {
switch (self, index) {
case (.`nil`, _):
return self
case (.cons(_, let tail), 0):
return tail
case (.cons(let head, let tail), let index):
return .cons(head, tail.remove(index: index - 1))
}
}
func update(index: Int, value: T) -> List<T> {
switch (self, index) {
case (.`nil`, _):
return self
case (.cons(_, let tail), 0):
return .cons(value, tail)
case (.cons(let head, let tail), let index):
return .cons(head, tail.update(index: index - 1, value: value))
}
}
func append(list: List<T>) -> List<T> {
switch self {
case .`nil`:
return list
case .cons(let head, let tail):
return List.cons(head, tail.append(list: list))
}
}
}
let list = List<Int>.cons(1, .cons(2, .cons(3, .`nil`)))
list.add(value: 100) // 1,2,3,100,nil
list.remove(index: 1) // 1,3,nil
list.update(index: 0, value: 100) // 100,2,3,nil
list.append(list: list) // 1,2,3,1,2,3,nilHigher order function
foldr and foldl is convolution function that scan value of List and make a computed result. map, filter is a function using foldr. Each value of List applied to function that passed by argument. The things that can be map over is called Functor. it is the abstraction of List<T> and Optional<T> and so on. Learning Functor might be good, if you are interested in. flatMap can keep the context of function and chain it.
extension List {
func foldr<R>(acc: R, f: (T,R) -> R) -> R {
switch self {
case .`nil`:
return acc
case .cons(let head, let tail):
return f(head, tail.foldr(acc: acc, f: f))
}
}
func foldl<R>(acc: R, f: (R,T) -> R) -> R {
switch self {
case .`nil`:
return acc
case .cons(let head, let tail):
return tail.foldl(acc: f(acc, head), f: f)
}
}
func map<R>(f: @escaping (T) -> R) -> List<R> {
return foldr(acc: List<R>.`nil`) { acc, list in
return List<R>.cons(f(acc), list)
}
}
func filter(f: @escaping (T) -> Bool) -> List<T> {
return foldr(acc: List<T>.`nil`, f: { acc, list in
if f(acc) {
return List<T>.cons(acc, list)
}
return list
})
}
func flatMap<R>(f: @escaping (T) -> List<R>) -> List<R> {
return foldr(acc: List<R>.`nil`, f: { acc, list in
return f(acc).append(list: list)
})
}
}
let list = List<Int>.cons(1, .cons(2, .cons(3, .`nil`)))
list.map { $0 * 10 } // "10,20,30,nil
list.filter { $0 % 2 == 0 } // 2,nil
list.flatMap { .cons($0, .cons($0, .`nil`)) } // 1,1,2,2,3,3,nil