Foldln в Haskell
Можно ли написать в Haskell что-то похожее на функции свертки во многих списках. Вот пример такой функции в Racket
#lang racket
(define (fold-left f i as . bss)
(if (or (null? as)
(ormap null? bss))
i
(apply fold-left
f
(apply f i (car as) (map car bss))
(cdr as)
(map cdr bss))))
(fold-left + 0 (list 1 2 3 4) (list 5 6 7 8))
(fold-left + 0 (list 1 2 3) (list 2 3 4) (list 3 4 5) (list 4 5 6))
(fold-left (λ (i v n s) (string-append i (vector-ref v n) s))
""
(list (vector "A cat" "A dog" "A mouse")
(vector "tuna" "steak" "cheese"))
(list 0 2)
(list " does not eat " "."))
В примере использования сгиба влево оцениваются значения 36, 42 и «Кошка не ест сыр». Мне кажется пока нет, но, возможно, есть какая-то хитрость, о которой я не подумал?
foldl' :: (b -> a -> b) -> b -> Tree a -> b существует. Это то, что вы ищете?
@willeM_VanOnsem Да, произвольная рекурсия до конца некоторого списка. В Racket аргументы var передаются функции через список. Итак, bss — это список списков. car и cdr возвращают голову и хвост соответственно.
@DanielWagner нет. Ваша функция принимает только 1 аргумент (исключая аккумулятор), а моя принимает произвольное количество аргументов.
@ostalyi foldl' принимает Tree, у которого может быть произвольное количество детей. Это просто другой синтаксис — f [a,b,c] вместо f a b c. (Ну, ладно, это Forest, а не Tree. Но адаптироваться легко — просто сложите складки.) Но если вам нужен синтаксис приложения-функции, то это дубликат.
Ответы 1
Прямого эквивалента нет, поскольку для этого потребуется создать список с (динамически) разнородными типами. Однако вы все равно можете добиться того же результата, используя другие операции в Haskell:
(fold-left + 0 (list 1 2 3 4) (list 5 6 7 8))
Было бы sum $ zipWith (+) [1,2,3,4] [5, 6, 7, 8]
(fold-left (λ (i v n s) (string-append i (vector-ref v n) s))
""
(list (vector "A cat" "A dog" "A mouse")
(vector "tuna" "steak" "cheese"))
(list 0 2)
(list " does not eat " "."))
Было бы
concat $ zipWith3 (\v n s -> concat [v!!n, s])
[ ["A cat", "A dog", "A mouse"]
, ["tuna", "steak","cheese"]
]
[0, 2]
[" does not eat ", "."]
zipWith3 можно расширить до любого произвольного (но фиксированного, поскольку статическая типизация) числа списков с помощью Applicative экземпляра ZipList:
zipWith<n> f l1 ... ln === f <$> ZipList l1 <*> ... <*> ZipList ln
По сути, вместо того, чтобы помещать все в одну большую складку, которая каким-то образом «знает», насколько глубоко она должна идти, вы просто явно записываете складки.
Основным камнем преткновения является возможность принимать функцию свертки произвольной арности и использовать тип функции для определения количества принимаемых аргументов списка. Я знаю, что Text.printf использует магию классов типов, чтобы тип возвращаемого значения зависел от строкового аргумента; Я не знаю, можно ли сделать что-то подобное с функцией сгиба.
Так что же это делает? Произвольная рекурсия?