Рекурсия против кратной эффективности - PullRequest
Новая
       51

Рекурсия против кратной эффективности

0 голосов
/ 26 ноября 2018

В известном руководстве по Haskell функция, которая находит значение по ключу в ассоциативном списке, сначала определяется следующим образом: 

findKey :: (Eq k) => k -> [(k,v)] -> Maybe v  
findKey key [] = Nothing  
findKey key ((k,v):xs) = if key == k  
                            then Just v  
                            else findKey key xs

Однако авторзатем утверждает, что этот тип «рекурсии из учебника» должен быть лучше реализован с использованием сгиба: 

findKey key = foldr (\(k,v) acc -> if key == k then Just v else acc) Nothing

Я обнаружил, что это сбивает с толку.Прав ли я, что:

  1. Функция на основе foldr всегда будет проходить через весь список до получения результата, тогда как первая немедленно остановится при обнаружении?
  2. Какследовательно, первая функция будет работать с бесконечным списком, а вторая - нет?

Мне кажется, что в эквивалентном определении действительно будет использоваться scanrвместо этого и возьмите первый результат, который не равен Nothing.(?)

Ответы [ 2 ]

0 голосов
/ 26 ноября 2018

foldr определяется так, что 

foldr cons z (x:xs) = cons x (foldr cons z xs)

, поэтому, если cons не использует второй аргумент, его значение не требуется.Поскольку Haskell является вызовом по необходимости, ненужные значения не оцениваются.

Так что нет, обе формулировки имеют одинаковые характеристики лени.

findKey key (x:xs)
  = foldr (\(k,v) r -> if key == k then Just v else r) Nothing (x:xs)
  = (\(k,v) r -> if key == k then Just v else r) x
      (foldr (\(k,v) r -> if key == k then Just v else r) Nothing xs)
  = case x of (k,v) -> if key == k then Just v else 
      (foldr (\(k,v) r -> if key == k then Just v else r) Nothing xs)

и поэтому, если удерживается key == k, рекурсивный вызов (для определения значения r) не запускается.

0 голосов
/ 26 ноября 2018
  1. Нет, когда функция \(k,v) acc -> ... вызывается foldr, рекурсивный вызов foldr предоставляется в качестве второго аргумента (т. Е. acc).Таким образом, имея в виду, что Haskell ленив, если acc не используется (т. Е. Если условие if истинно), рекурсивный вызов не происходит и обход прекращается.
  2. Оба работают нормальнос бесконечными списками.
...