Что лучше использовать охранники, чем шаблоны для рекурсивных функций в Haskell? - PullRequest
Новая
       29

Что лучше использовать охранники, чем шаблоны для рекурсивных функций в Haskell?

8 голосов
/ 21 мая 2011

Мне просто интересно узнать о функции рекурсии, которую я выкладываю в Haskell.Как правило, лучше использовать охранники, чем шаблоны для функций рекурсии?

Я просто не уверен в том, что такое лучший макет, но я знаю, что шаблоны лучше при определении таких функций: 

units :: Int -> String

units 0 = "zero"
units 1 = "one"

гораздо предпочтительнее 

units n
    | n == 0 = "zero"
    | n == 1 = "one"

Я просто не уверен, когда дело доходит до рекурсии относительно того, является ли это одинаковым или другим.

Просто не совсем уверен в терминологии: я использую что-то вроде этого: 

f y [] = [] 
f y (x:xs) 
    | y == 0 = ...... 
    | otherwise = ......

или это будет лучше? 

f y [] = [] 
f 0 (x:xs) = 
f y (x:xs) =

Ответы [ 5 ]

9 голосов
/ 21 мая 2011

Мое эмпирическое правило будет таким:

  • Используйте сопоставление с образцом, когда охранник будет простой == проверкой.

При рекурсии вы обычно проверяете базовый вариант. Поэтому, если ваш базовый случай - простая проверка ==, используйте сопоставление с образцом.

Так что я обычно делаю это: 

map f [] = []
map f (x:xs) = f x : map f xs

Вместо этого (null просто проверяет, является ли список пустым. В основном это == []): 

map f xs | null xs   = []
         | otherwise = f (head xs) : map f (tail xs)

Сопоставление с образцом призвано сделать вашу жизнь проще, имхо, поэтому в конце вы должны сделать то, что имеет для вас смысл. Если вы работаете с группой, делайте то, что имеет смысл для группы.

[обновление]

Для вашего конкретного случая я бы сделал что-то вроде этого: 

f _ []      = []
f 0 _       = ...
f y (x:xs)  = ...

Матричные соответствия, как и охранники, падают сверху вниз, останавливаясь на первом определении, соответствующем вводу. Я использовал символ подчеркивания, чтобы указать, что для первого совпадения с шаблоном мне было все равно, каков аргумент y, а для второго совпадения с шаблоном мне было все равно, что это за аргумент списка (хотя, если вы используйте список в этом вычислении, тогда вы не должны использовать подчеркивание). Так как это все еще довольно простые == -подобные проверки, я лично буду придерживаться сопоставления с образцом.

Но я думаю, что это вопрос личных предпочтений; Ваш код отлично читается и корректен как есть. Если я не ошибаюсь, когда код скомпилирован, в конечном итоге оба элемента защиты и сопоставления с образцом превращаются в операторы case.

4 голосов
/ 21 мая 2011

Простое правило

  • Если вы рекурсивно обрабатываете структуру данных, используйте сопоставление с шаблоном
  • Если ваше рекурсивное условие более сложное, используйте охранники.

Обсуждение

По сути, это зависит от теста, который вы хотите провести для защиты рекурсии.Если это проверка структуры типа данных, используйте сопоставление с образцом, поскольку это будет более эффективным, чем избыточное тестирование на равенство.

Для вашего примера сопоставление с образцом в целых числах, очевидно, чище и эффективнее: 

units 0 = "zero"
units 1 = "one"

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

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

2 голосов
/ 21 мая 2011

В ответах до сих пор не упоминается преимущество сопоставления с образцом, которое для меня является наиболее важным: способность безопасно реализовывать все функции.

При сопоставлении с образцом вы можете безопасно получить доступ к внутренней структуре объекта, не опасаясь, что этот объект будет чем-то другим. Если вы забыли некоторые шаблоны, компилятор может предупредить вас (к сожалению, это предупреждение по умолчанию отключено в GHC).

Например, при написании этого: 

map f xs | null xs   = []
         | otherwise = f (head xs) : map f (tail xs)

Вы вынуждены использовать неполные функции head и tail, тем самым рискуя жизнью вашей программы. Если вы допустили ошибку в условиях охраны, компилятор не сможет вам помочь.

С другой стороны, если вы допустили ошибку при сопоставлении с образцом, компилятор может выдать вам ошибку или предупреждение в зависимости от того, насколько серьезной была ваша ошибка.

Некоторые примеры: 

-- compiles, crashes in runtime
map f xs | not (null xs)   = []
         | otherwise = f (head xs) : map f (tail xs)

-- does not have any way to compile
map f (h:t) = []
map f [] = f h : map f t


-- does not give any warnings
map f xs = f (head xs) : map f (tail xs)

-- can give a warning of non-exhaustive pattern match
map f (h:t) = f h : map f t
2 голосов
/ 21 мая 2011

@ Дэн прав: это в основном вопрос личных предпочтений и не влияет на сгенерированный код. Этот модуль: 

module Test where

units :: Int -> String
units 0 = "zero"
units 1 = "one"

unitGuarded :: Int -> String
unitGuarded n
  | n == 0 = "zero"
  | n == 1 = "one"

производится следующее ядро: 

Test.units =
  \ (ds_dkU :: GHC.Types.Int) ->
    case ds_dkU of _ { GHC.Types.I# ds1_dkV ->
    case ds1_dkV of _ {
      __DEFAULT -> Test.units3;
      0 -> Test.unitGuarded2;
      1 -> Test.unitGuarded1
    }
    }

Test.unitGuarded =
  \ (n_abw :: GHC.Types.Int) ->
    case n_abw of _ { GHC.Types.I# x_ald ->
    case x_ald of _ {
      __DEFAULT -> Test.unitGuarded3;
      0 -> Test.unitGuarded2;
      1 -> Test.unitGuarded1
    }
    }

Точно так же, за исключением другого случая по умолчанию, который в обоих случаях является ошибкой сопоставления с образцом. GHC даже обобщил строки для соответствующих случаев.

2 голосов
/ 21 мая 2011

На самом деле нет жестких и быстрых правил, поэтому ответы, которые вы получили, были немного туманными. Некоторые решения просты, например, сопоставление с образцом на [] вместо защиты с f xs | null xs = ... или, боже упаси, f xs | length xs == 0 = ..., что ужасно во многих отношениях. Но когда нет практической проблемы, просто используйте то, что делает код более понятным.

В качестве примера рассмотрим следующие функции (которые на самом деле ничего полезного не делают, просто служат иллюстрациями): 

f1 _ [] = [] 
f1 0 (x:xs) = [[x], xs]
f1 y (x:xs) = [x] : f1 (y - 1) xs

f2 _ [] = []
f2 y (x:xs) | y == 0    = calc 1 : f2 (- x) xs
            | otherwise = calc (1 / y) : f2 (y * x) xs
  where calc z = x * ...

В f1 отдельные шаблоны подчеркивают, что рекурсия имеет два базовых случая. В f2 охранники подчеркивают, что 0 - это просто особый случай для некоторых вычислений (большинство из которых выполняется calc, определенным в предложении where, совместно используемом обеими ветвями охранника) и не меняет Структура расчета.

...