この記事はScalaプログラミングスタイル集をSwift2.0化するものです。詳しくはそちらをご覧ください。
手続きプログラミング
func fac(n: Int) -> Int {
var result = 1
for i in 1...n {
result *= i
}
return result
}
普通の再帰
func fac(n: Int) -> Int {
if n == 0 {
return 1
} else {
return n * fac(n - 1)
}
}
パターンマッチ
func fac(n: Int) -> Int {
switch n {
case 0:
return 1
default: //case _:でも通る
return n * fac(n - 1)
}
}
Swiftのパターンマッチイコールただの(割と自由に書ける)switch文という認識が抜けない。これじゃあ普通の再帰と一緒なのだが。
末尾再帰
func facAcc(acc: Int, n: Int) -> Int {
if n == 0 {
return acc
} else {
return facAcc(n * acc, n: n - 1)
}
}
func fac(n: Int) -> Int {
return facAcc(1, n: n)
}
facAccはローカル関数化できる、が、Swift1.2でやるとLocal functions cannot reference themselvesとか言われる。
func fac(n: Int) -> Int {
func facAcc(acc: Int, n: Int) -> Int {
if n == 0 {
return acc
} else {
return facAcc(n * acc, n: n - 1)
}
}
return facAcc(1, n: n)
}
継続渡し
そもそもの合成関数をざっくり用意するところから始めないといけない。
infix operator ○ { }
func ○<T,U,V>(lhs: U -> V, rhs: T -> U) -> T -> V {
return {x in lhs(rhs(x))}
}
↑を踏まえると
func facCps(k: Int -> Int, n: Int) -> Int {
if n == 0 {
return k(1)
} else {
return facCps(k ○ {n * $0}, n: n - 1)
}
}
func fac(n: Int) -> Int {
return facCps({$0}, n: n)
}
Yコンビネータ
func Y<T, U>(x: T, f: (T, (T -> U)) -> U) -> U {
return f(x){y in Y(y, f: f)}
}
func fac(n: Int) -> Int {
return Y(n){ n, f in
if n == 0 {
return 1
} else {
return n * f(n - 1)
}
}
}
trailing closureを意識して本家とは仮引数の位置を代わってもらってみた。
foldLeft
ScalaのfoldLeftはSwiftのreduceだしScalaのreduceは……あれ?
func fac(n: Int) -> Int {
return (1...n).reduce(1, combine: *)
//return (1...n).reduce(1){$0 * $1}
}
自力でfoldLeft(Swiftでいうところのreduce)を実装すると次のような感じ。reduceと同様SequenceTypeに対して実装してみる。
extension SequenceType {
func foldLeft<U>(initial: U, combine: (U, Self.Generator.Element) -> U) -> U {
var result = initial
for element in self {
result = combine(result, element)
}
return result
}
}
func fac(n: Int) -> Int {
return (1...n).foldLeft(1, combine: *)
}
foldRight
ダメなfoldRightの場合
extension SequenceType {
func foldRight<U>(initial: U, combine: (Self.Generator.Element, U) -> U) -> U {
var result = initial
let array = self.reverse()
for element in array {
result = combine(element, result)
}
return result
}
}
func fac(n: Int) -> Int {
return (1...n).foldRight(1, combine: *)
}
無限Stream対応版は種々のエラーに阻まれてなかなか大変なので省略。
ポイントフリー
func fac(x: Int) -> Int {
return ({(array: [Int]) in array.reduce(1, combine: *)} ○ {(x: Int) in Array(1...x)})(x)
}
unfold
func unfold<T, U>(p: T -> Bool, h: T -> U, t: T -> T, a: T) -> Array<U> {
if p(a) {
return [U]()
} else {
return [h(a)] + unfold(p, h: h, t: t, a: t(a))
}
}
func fac(n: Int) -> Int {
return ({(array: [Int])in array.foldRight(1, combine: *)} ○ {(n: Int) in unfold({$0 == 0}, h: {x in x}, t: {$0 - 1}, a: n)})(n)
}
Hylomorphism
func hylo<T,U,V>(v: V, f: (U, V) -> V, g: T -> (U, T), p: T -> Bool, t: T) -> V {
if p(t) {
return v
} else {
let (u, t_) = g(t)
return f(u, hylo(v, f: f, g: g, p: p, t: t_))
}
}
func fac(n: Int) -> Int {
return hylo(1, f: *, g: {n in (n, n - 1)}, p: {$0 == 0}, t: n)
}
Paramorphism
func paraInt<T>(a: T, n: Int, f: (Int, T) -> T) -> T {
if (n == 0) {
return a
} else {
return f(n, paraInt(a, n: n - 1, f: f))
}
}
func fac(n: Int) -> Int {
return paraInt(1, n: n){n, m in n * m}
}
余談としてParamorphismの代表例、tailsが載っている。
func paraList<T, U>(b: U, array: [T], f: (T, [T], U) -> U) -> U {
if array.isEmpty {
return b
} else {
return f(array.first!, array, paraList(b, array: Array(array[1..<array.count]), f: f))
}
}
func tails<T>(array: [T]) -> [[T]] {
return paraList([[T]](), array: array){x, xs, tls in
return [xs] + tls
}
}
ただしこの実装だと出力がたとえば
[[1, 2], [2]]
となる。ScalaだとList(List(1, 2), List(2), List())。リスト構造じゃないのでしょうがない…?あと、部分配列の取り出しが気持ち悪い。Swiftzとか使うと綺麗になるのかもしれない。
始代数、終余代数
量が多すぎ。Scalaに譲る
ここまで理解できていれば、Swiftを実務で使うのに十分な実力があると思います。(?)