Неисключающая ошибка при реализации церковных цифр в Swift 3

Question

Неисключающая ошибка при реализации церковных цифр в Swift 3

Я пытаюсь внедрить церковные цифры в Swift 3. В настоящее время у меня есть:

func numToChurch(n: Int) -> ((Int) -> Int) -> Int {

    return { (f: (Int) -> Int) -> (Int) -> Int in
        return { (x : Int) -> Int in
            return f(numToChurch(n: n - 1)(f)(x))
        }
    }
}

func churchToNum(f: ((Int) -> Int) -> (Int)-> Int) -> Int {
    return f({ (i : Int) -> Int in
        return i + 1
    })(0)
}

В этой строке в моей функции numToChurch:

return f(numToChurch(n: n - 1)(f)(x))

Я продолжаю получать ошибку во время компиляции, что "Закрытие неэкранирующего параметра 'f' может позволить ему сбежать". В качестве быстрого исправления я принял рекомендуемые изменения, включив в них @escaping:

func numToChurch(n: Int) -> ((Int) -> Int) -> Int {

    return { (f: @escaping (Int) -> Int) -> (Int) -> Int in
        return { (x : Int) -> Int in
            return f(numToChurch(n: n - 1)(f)(x))
        }
    }
}

Но даже после внесения изменений мне все время сообщают об одной и той же ошибке, и он рекомендует добавить еще один @escaping после "f:". Я понимаю, что это связано с маркировкой параметров функции как @escaping, чтобы сообщить компилятору, что параметры могут быть сохранены или получены для функционального программирования. Но я не понимаю, почему я продолжаю получать эту ошибку.

Первоначальный неотступающий вопрос решен

Помогите с пониманием церковного кодирования в Swift, продолжение:

func zero(_f: Int) -> (Int) -> Int {
    return { (x: Int) -> Int in
        return x
    }
}

func one(f: @escaping (Int) -> Int) -> (Int) -> Int {
    return { (x: Int) in
        return f(x)
    }
}

func two(f: @escaping (Int) -> Int) -> (Int) -> Int {
    return { (x: Int) in
        return f(f(x))
    }
}

func succ(_ f: Int) -> (@escaping (Int) -> Int) -> (Int) -> Int {
    return { (f : @escaping ((Int) -> Int)) -> Int in
        return { (x : Int) -> Int in
            return f(n(f)(x))
        }
    }
}


func sum(m: @escaping ((Int) -> (Int) -> Int)) -> ((Int) -> (Int) -> Int) -> (Int) -> (Int) -> Int {
    return { (n: @escaping ((Int) -> Int)) -> (Int) -> (Int) -> Int in
        return { (f: Int) -> (Int) -> Int in
            return { (x: Int) -> Int in
                return m(f)(n(f)(x))
            }
        }
    }

4

swift functional-programming swift3 church-encoding church

Источник

user6627782 01 окт '16 в 19:34

2 ответа

Решение

@escaping является частью типа аргумента, поэтому вам нужно сделать это следующим образом:

func numToChurch(n: Int) -> (@escaping (Int) -> Int) -> (Int) -> Int {
//                           ^~~~~~~~~

Полный рабочий код:

func numToChurch(n: Int) -> (@escaping (Int) -> Int) -> (Int) -> Int {
//                           ^~~~~~~~~                        ^~~~~~
    return { (f: @escaping (Int) -> Int) -> (Int) -> Int in
//               ^~~~~~~~~
        if n == 0 {
            return { x in x }
        } else {
            return { (x : Int) -> Int in
                return f(numToChurch(n: n - 1)(f)(x))
            }
        }
    }
}

func churchToNum(f: (@escaping (Int) -> Int) -> (Int) -> Int) -> Int {
//                   ^~~~~~~~~
    return f({ (i : Int) -> Int in
        return i + 1
    })(0)
}

let church = numToChurch(n: 4)
let num = churchToNum(f: church)

Замечания:

Ваш возвращаемый тип numToChurch неправильно даже без @escaping часть. Вам не хватает -> Int,
Я добавил базу n == 0 дело в numToChurchиначе это будет бесконечная рекурсия.
Так как результат numToChurch имеет закрывающее закрытие, ту же аннотацию необходимо добавить к churchToNum также.

3

Источник

user224671 03 окт '16 в 17:17

Другие вопросы по тегам swift functional-programming swift3 church-encoding church

user97337 03 окт '16 в 17:10 2016-10-03 17:10 · Accepted Answer · 2016-10-03 17:10

Вы используете карри для многопараметрических функций. Это не очень естественный способ выразить вещи в Swift, и это усложняет ситуацию. (Swift не является функциональным языком программирования.)

Как сказано в вашей статье: "Все церковные цифры - это функции, которые принимают два параметра". Так сделай это. Сделайте это двухпараметрической функцией.

typealias Church = (_ f: ((Int) -> Int), _ x: Int) -> Int

Это функция, которая принимает два параметра, функцию и ее аргумент.

Теперь вы хотите обернуть аргумент в функцию N раз:

// You could probably write this iteratively, but it is pretty elegant recursively 
func numToChurch(_ n: Int) -> Church {
    // Church(0) does not apply the function
    guard n > 0 else { return { (_, n) in n } }

    // Otherwise, recursively apply the function
    return { (f, x) in
        numToChurch(n - 1)(f, f(x))
    }
}

И возвращение - это просто применение функции:

func churchToNum(_ church: Church) -> Int {
    return church({$0 + 1}, 0)
}

Просто опираясь на это, вы можете это карри (и я думаю, я просто говорю, что @kennytm также ответил). Карринг в Swift немного сложнее:

typealias Church = (@escaping (Int) -> Int) -> (Int) -> Int

func numToChurch(_ n: Int) -> Church {
    // Church(0) does not apply the function
    guard n > 0 else { return { _ in { n in n } } }

    return { f in { x in
        numToChurch(n - 1)(f)(f(x))
        }
    }
}

func churchToNum(_ church: Church) -> Int {
    return church({$0 + 1})(0)
}

Есть очень резонный вопрос: "Зачем мне @escaping во втором случае, но не в первом?"Ответ таков: когда вы передаете функцию в кортеж, вы уже избежали ее (сохраняя в другой структуре данных), поэтому вам не нужно отмечать ее @escaping снова.

На ваши дальнейшие вопросы, использование typealias значительно упрощает эту проблему и помогает вам более четко продумывать ваши типы.

Так каковы параметры нуля? Ничего такого. Это константа. Так какой должна быть его подпись?

func zero() -> Church

Как мы это реализуем? Мы применяем f ноль раз

func zero() -> Church {
    return { f in { x in
        x
        } }
}

Один и два почти идентичны:

func one() -> Church {
    return { f in { x in
        f(x)
        } }
}

func two() -> Church {
    return { f in { x in
        f(f(x))
        } }
}

Что является подписью succ? Он берет церковь и возвращает церковь

func succ(_ n: @escaping Church) -> Church {

Поскольку это Swift, нам нужно немного подтолкнуть, добавив @escaping а также _ чтобы сделать вещи более естественными. (Swift не является функциональным языком; он по-разному разбирает проблемы. Составление функций не является его естественным состоянием, поэтому изобилие синтаксиса не должно нас шокировать.) Как реализовать? Применить еще один f в n:

func succ(_ n: @escaping Church) -> Church {
    return { f in { x in
        let nValue = n(f)(x)
        return f(nValue)
        } }
}

И снова, какова природа sum? Ну, у нас настроение карри, так что это означает, что это функция, которая берет Церковь и возвращает функцию, которая берет Церковь и возвращает Церковь.

func sum(_ n: @escaping Church) -> (@escaping Church) -> Church

Опять же, требуется небольшой дополнительный синтаксис, потому что Swift. (И, как указано выше, я добавил дополнительную привязку let, чтобы сделать кусочки немного более четкими.)

func sum(_ n: @escaping Church) -> (@escaping Church) -> Church {
    return { m in { f in { x in
        let nValue = n(f)(x)
        return m(f)(nValue)
        } } }
}

Глубокий урок здесь - сила Church typealias. Когда вы пытаетесь думать о церковных числах как о "функциях, которые бла-бла-бла", вы быстро теряетесь в карри и синтаксисе. Вместо этого, абстрагируйте их от "церковных чисел" и просто подумайте о том, что должна принимать и возвращать каждая функция. Помните, что церковный номер всегда является функцией, которая принимает Int и возвращает Int. Он никогда не растет и не уменьшается от этого, независимо от того, сколько раз он был вложенным.

Стоит взять этот пример в нескольких других направлениях, потому что мы можем воспроизвести некоторые более глубокие идеи FP, а также то, как на самом деле должен быть написан Swift (которые не совпадают....)

Во-первых, написание церковных чисел в заостренном стиле... не элегантно. Это просто плохо. Церковные числа определены с точки зрения функциональной композиции, а не приложения, поэтому они должны быть написаны в бессмысленном стиле IMO. В основном везде, где вы видите { f in { x in ...} }Это просто уродливо и чрезмерно синтаксис. Поэтому мы хотим функциональную композицию. Хорошо, мы можем покопаться в некоторых экспериментальных функциях stdlib и получить это

infix operator ∘ : CompositionPrecedence

precedencegroup CompositionPrecedence {
    associativity: left
    higherThan: TernaryPrecedence
}

public func ∘<T, U, V>(g: @escaping (U) -> V, f: @escaping (T) -> U) -> ((T) -> V) {
    return { g(f($0)) }
}

Теперь, что это делает для нас?

func numToChurch(_ n: Int) -> Church {
    // Church(0) does not apply the function
    guard n > 0 else { return zero() }
    return { f in f ∘ numToChurch(n - 1)(f) }
}

func succ(_ n: @escaping Church) -> Church {
    return { f in f ∘ n(f) }
}

func sum(_ n: @escaping Church) -> (@escaping Church) -> Church {
    return { m in { f in
        n(f) ∘ m(f)
        } }
}

Поэтому нам не нужно говорить о x больше. И мы гораздо мощнее фиксируем сущность церковных чисел, ИМО. Суммирование их эквивалентно функциональной композиции.

Но все это говорит, ИМО, это не великий Свифт. Свифт хочет структуру и методы, а не функции. Это определенно не хочет функцию верхнего уровня под названием zero(), Это ужасный Свифт. Так, как мы осуществляем церковные числа в Свифте? Подняв в тип.

struct Church {
    typealias F = (@escaping (Int) -> Int) -> (Int) -> Int
    let applying: F

    static let zero: Church = Church{ _ in { $0 } }

    func successor() -> Church {
        return Church{ f in f ∘ self.applying(f) }
    }

    static func + (lhs: Church, rhs: Church) -> Church {
        return Church{ f in lhs.applying(f) ∘ rhs.applying(f) }
    }
}

extension Church {
    init(_ n: Int) {
        if n <= 0 { self = .zero }
        else { applying = { f in f ∘ Church(n - 1).applying(f) } }
    }
}

extension Int {
    init(_ church: Church) {
        self = church.applying{ $0 + 1 }(0)
    }
}

Int(Church(3) + Church(7).successor() + Church.zero) // 11