Как понять каррирование и частичное применение функции? В чём их различия?

Question

[plyk]

Как я понял, в хаскелле все функции > 1 аргумента становятся каррироваными. Как понять эту каррированность?

Допустим

add :: Int -> Int -> Int
add x y = x + y

При add 2 2 как я понял она переделается в add :: Int -> (Int -> Int)
И вот как это понять? Ну допустим функция add берёт первый аргумент 2 и возвращает функцию add которая ожидает второй аргумент 2? Что вообще происходит в теле возвращаемой функции? Неужели что -то вроде

add :: Int -> Int
add y = 2 + y

А если у функции аргументов намного больше?

А как вообще работает частичное применение? Что это такое?

Answer 1

[Vindicar]

plyk, вот частичное применение в упрощённом варианте для двух аргументов.

def partial(func: typing.Callable[[int, int], int], arg1: int) -> typing.Callable[[int], int]:
    def wrapper(arg2: int) -> int:
        return func(arg1, arg2)
    return wrapper

def add (x: int, y: int) -> int:
    return x + y

def div(x: int, y:int) -> int:
    return x // y

add_42 = partial(add, 42)
print(add_42(3))  # 42 + 3 = 45

div_120 = partial(div, 120)
print(div_120(30))  # 120 // 30 = 4

А каррирование - по сути, каррированная функция вместо выбрасывания ошибки "недостаточно аргументов" возвращает частично применённую функцию для себя и указанных аргументов. Вот очень упрощённая реализация для функции двух аргументов:

def curry(func: typing.Callable[[int, int], int]) -> typing.Callable:
    def wrapper(*args):
        if len(args) == 2:
            return func(*args)
        elif len(args) == 1:
            return partial(func, args[0])
        else:
            raise Exception('Invalid arguments')
    return wrapper

curried_add = curry(add)
print(curried_add(32, 23))  # 55
add_30 = curried_add(30)
print(add_30(70))  # 30 + 70 = 100

Comments

[Алан Гибизов]

А откуда во втором коде partial взялся? Из первого кода, чтоль?

[Vindicar]

Алан Гибизов, ага, как и add(). Мне так проще всего показалось пояснить.

[Алан Гибизов]

Vindicar, любопытно.
Получается, при помощи partial мы создаем «экземпляр функции»?

[Vindicar]

Алан Гибизов, ну да. Строго говоря, в питоне def - это оператор создания функции. Поэтому при каждом его выполнении создаётся новый объект-функция. И эти объекты будут ссылаться на экземпляр locals для вышележащей функции. Как следствие, если на один вызов вышележащей функции создаётся одна вложенная, то экземпляры locals будут разные. Если в одном вызове вышележащей функции создаётся несколько вложенных (скажем, циклом), то они будут ссылаться на один и тот же экземпляр locals.
По крайней мере, я так эту механику понимаю.

[Алан Гибизов]

Vindicar, сегодня вычитал, что вроде как это называется замыканием. Или это не оно?

[Vindicar]

Алан Гибизов, ну да, это оно.

Answer 2

[Александр Скуснов]

1) скобки в описании типа расставляются вправо, так что может быть любое количество аргументов:
fun:: a -> (a -> (a -> a))
2) частичное применение означает, что функции можно скармливать аргументы по одному в любом количестве.
(в режиме оператора можно подсунуть второй, а первый - потом).
3) про каррирование. Есть вид передачи параметров в других языках fun(p1, p2, p3). На Haskell это передача одной группы (кортежа). Есть функции высшего порядка curry и uncurry, которые вашу функцию переводят в противоположный тип.

Answer 3

[Александр Павлюк]

Наверное, вы имели ввиду add 2, тогда мы применим только первый аргумент функции. Когда мы так делаем, на выходе получаем функцию с одним аргументом, потому что первый аргумент уже равен 2. Можете считать, что он просто сохранен внутри этой функции, чтобы быть использованным, когда функция будет полностью применена.

Что вообще происходит в теле возвращаемой функции?

Так немного некорректно рассуждать, потому что компилятор может по-разному оптимизировать внутренность функции.

Но если вам будет проще понять, можно представить, что у нас не Хаскель, а обычный императивный язык. Тогда частичное применение можно эмулировать с помощью замыкания:

func main() {
	fmt.Println(sum(1, 2))

	carried := carry(sum, 1)
	fmt.Println(carried(2))
}

func sum(a, b int) int {
	return a + b
}

func carry(fn func(int, int) int, a int) func(int) int {
	return func(b int) int {
		return fn(a, b)
	}
}

https://go.dev/play/p/dp6W3U5bSGq

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

Comments

[plyk]

Я ничего не понял. Я только начал изучать язык и не могу понять как вашей терминологии так и непонятного приведённого для меня кода. Похожего на C

[Александр Павлюк]

plyk, какой язык вам лучше всего знаком? Приведу аналогию на нем.

[Александр Павлюк]

И будет лучше, если скажете, какие именно термины не поняли. Мне сложно будет перефразировать текст, не зная, что именно вызвало трудности.

[plyk]

Александр Павлюк, желательно на околопитоновском псевдокоде с минимум скобок. Я не понял что такое замыкание.

Правильно ли я понял что можно например с
plus :: Int -> Int-> Int

Сделать

let plus_dva = plus 2 

Prelude: plus_dva 2
: 2

?

[Александр Павлюк]

plyk, да, абсолютно правильно поняли. plus_dva будет функцией, которая прибавляет 2 к любому переданному ей числу.