Как оцениваются охранники Хаскелла?

Question

Я делаю 99 Haskell проблемы и в одном из решений я наткнулся на следующий код:

pack' [] = [] 
pack' [x] = [[x]] 
pack' (x:xs) 
    | x == head h_p_xs = (x:h_p_xs):t_p_hs 
    | otherwise   = [x]:p_xs 
    where p_xs@(h_p_xs:t_p_hs) = pack' xs 

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

Answer 1

мне интересно, когда пакет»вызывается в первом охранником

x == head h_p_xs охранником заставляет оценку h_p_xs, которая вызывает рекурсивный вызов.

и если это общий шаблон в Haskell кода для ссылки на голову и хвост списка вернулся из вызова функции.

Я думаю, что это довольно распространенный образец. Вы также можете найти варианты, используя вместо этого case pack' xs of ... или let ... = pack' xs in ....Обратите внимание, что использование let или where с таким шаблоном, как h_p_xs:t_p_xs, приведет к ошибке выполнения во время нахождения пустого списка. Этот код осторожен, чтобы рекурсивный вызов не возвращал список emlty.

Есть несколько вызовов, чтобы упаковать» на любых уровнях рекурсии

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

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

Для сравнения, ниже код эквивалентен, но привел бы к экспоненциальным сложности (!)

... 
where p_xs = h_p_xs:t_p_hs 
     h_p_xs = head (pack' xs) 
     t_p_xs = tail (pack' xs) 

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

И это быстрое решение?

Да. Ожидается, что он будет работать в линейном времени на входе.

Answer 2

Это обычный способ ссылки на головку, если код делает его более удобочитаемым. Конечно, вы можете сделать это, выполнив на последней строке что-то вроде

p_xs@( (h_p_x : h_p_xs) : t_p_hs) = pack' xs 

вместо

p_xs@(h_p_xs : t_p_hs) = pack' xs 

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

| x == head h_p_xs = (x : h_p_x: h_p_xs):t_p_hs 

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

Answer 3

пакет ', кажется, работает как Data.List.group - Он группирует последовательные равные элементы в списке. Итак, pack '[1,1,3,2,2] должен возвращать [[1,1], [3], [2,2]].

Соответствие шаблону является идиоматическим haskell. Здесь, в заявлении,

h_p_xs:t_p_hs = pack' hs 

Мы знаем, что пакет hs возвращает список. Таким образом, h_p_xs сопоставляется с его головой, а t_p_hs сопоставляется с его хвостом. И LHS, и RHS должны иметь такую ​​же структуру, как здесь (обе стороны здесь имеют структуру списка) для сопоставления шаблонов для работы в Haskell. Здесь p_xs соответствует всем RHS (@ pattern). Итак, да, это очень распространенная идиома в Haskell.

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

На любом уровне есть максимальный один рекурсивный вызов pack ', поэтому сложность по времени - это O (n) в длине списка. Быть быстрым.