Рекурсия или фолд в хаскеле - PullRequest
Новая
       42

Рекурсия или фолд в хаскеле

4 голосов
/ 28 марта 2019

Я изучаю немного функционального программирования с использованием haskell, и я пытаюсь пройтись по некоторым концепциям, повторно внедрив некоторые библиотечные функции.

У меня есть вопрос, хотя, главным образом, относительно того, когда лучше выбирать рекурсию вместо итерации. Например, при переопределении функции «все» я могу выбирать между: 

all1 :: (a -> Bool) -> [a] -> Bool
all1 p xs = foldr (\x acc -> acc && p x) True xs 

all2 :: (a -> Bool) -> [a] -> Bool
all2 p (x:xs) 
  | p x == False = False
  | otherwise    = all2 p xs

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

Итак, этот компромисс - это то, что всегда есть? Неужели я что-то неправильно понимаю в рекурсии и фальцовке?

Спасибо!

Ответы [ 2 ]

2 голосов
/ 28 марта 2019

Давайте посмотрим, по кирпичику, может ли решение на основе foldr замкнуть накоротко. Для начала, (&&) определяется как это : 

(&&)                    :: Bool -> Bool -> Bool
True  && x              =  x
False && _              =  False

Учитывая второе предложение и, благодаря лени, второй аргумент (&&) игнорируется, если первый аргумент False - другими словами, он закорачивает.

Далее это foldr для списков : 

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

Если y `k` go ys можно оценить, не глядя на go ys, рекурсивного вызова не будет, и сгиб в целом будет сокращен.

В all1 бинарная операция \x acc -> acc && p x. Это недостаточно для наших целей, поскольку передача acc (что соответствует go ys в определении foldr) в качестве первого короткого замыкания аргумента (&&) приводит к тому, что весь список используется независимо от того, из того, что p x оказывается. Однако не все потеряно: обмен аргументов на (&&) ... 

all3 :: (a -> Bool) -> [a] -> Bool
all3 p xs = foldr (\x acc -> p x && acc) True xs

... дает нам желаемое короткое замыкание.

2 голосов
/ 28 марта 2019

foldr определяется следующим образом: 

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

Если вы вставите это определение в all1, вы увидите, что результат также рекурсивен.Следовательно, он просто не является явно рекурсивным, поскольку он скрывает рекурсию внутри foldr.

Вариант foldr является одновременно более экономичным и более экономичным, так как foldr имеет правила для объединения списков (оптимизация для удаления промежуточных списков), который all1 получает бесплатно.

Чтобы сделать работу с короткими замыканиями, просто измените acc && p x на p x && acc.С foldr это перестанет проходить список, как только получит False результат.С foldl или foldl', даже если ваша функция сворачивания закорачивается, она все равно должна пройти по остальной части списка.

Резюме: Использование foldr более эффективно, чем либо foldl,foldl' или явным образом повторяется в вашей собственной функции.Хорошим простым тестом для этого является выполнение +set :s в GHCi, а затем сравнение производительности в списке (False:replicate 10000000 True).

...