Haskell pattern-matching idiom

Question

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

add Zero x = x 
add (P x) y = next $ add (prev $ P x) y 
add (N x) y = prev $ add (next $ N x) y 

или

add Zero x = x 
add x y = case x of 
    P _ -> next $ add (prev x) y 
    _ -> prev $ add (next x) y 

В то время как первый путь короче, что-то во втором пути обращается ко мне больше.

Каков предпочтительный способ сделать это?

Answer 1

Использование as-patterns.

add Zero y = y 
add x@(P _) y = next $ add (prev x) y 
add x@(N _) y = prev $ add (next x) y 

Я бы также рассмотреть вопрос о абстрагировании из общей структуры ваших двух рекурсивных ветвей, отметив, что вы просто поменять места ролей функций prev и next в зависимости от того, x является положительным или отрицательным:

add Zero x = x 
add x y = f $ add (g x) y 
    where (f, g) = case x of 
         P _ -> (next, prev) 
         N _ -> (prev, next) 

Answer 2

Об этом стиле:

add Zero x = x 
add x y = case x of 
    P _ -> next $ add (prev x) y 
    _ -> prev $ add (next x) y 

с положительной стороны, это позволяет избежать некоторые повторения, что хорошо.

С отрицательной стороны, case выглядит не исчерпывающим с первого взгляда. Действительно, чтобы убедить себя, что совпадение шаблонов действительно является исчерпывающим, мы должны рассуждать о возможных значениях для x в case x of и видеть, что во время выполнения, которое не может быть Zero, потому что это было обработано выше. Это требует гораздо более умственных усилий, чем первый фрагмент, который явно исчерпывающий.

Хуже, когда вы включаете предупреждения, как мы всегда должны делать, GHC жалуется, так как не убежден, что case является исчерпывающим.

Лично я желаю, чтобы дизайнеры Haskell полностью запретили неисчерпаемые матчи. Я бы использовал -Werror-on-non-exhaustive-matches, если бы он был. Я хотел бы, чтобы меня заставили писать, например.

case something of 
    A -> ... 
    B -> ... 
    _ -> error "the impossible happened" 

, не имея последней ветви, которая молча вводится компилятором для меня.

Answer 3

Рассмотрим использование math-style definition of integers как конгруэнции классы пар натуралий по отношению эквивалентности:

{((a,b), (c,d)) | b+c == d+a} 

Интуиция является то, что пара натуралий (a,b) представляет b-a. Как упоминалось в статье в Википедии, это часто уменьшает количество особых случаев по сравнению с определением «0/положительное/отрицательное». В частности, операция сложения вы спрашиваете о реализации становится один вкладыш:

-- both Int and Integer are taken 
data Int' = Int Nat Nat 

instance Num Int' where 
    -- b-a + d-c = (b+d)-(a+c) 
    Int a b + Int c d = Int (a + c) (b + d) 

Это своего рода удовольствие работать через различные операции с этим представлением.Например, Eq могут быть реализованы с помощью приведенного выше уравнения, и Ord похож:

instance Eq Int' where 
    -- b-a == d-c = b+c == d+a 
    Int a b == Int c d = b+c == d+a 

instance Ord Int' where 
    -- compare (b-a) (d-c) = compare (b+c) (d+a) 
    compare (Int a b) (Int c d) = compare (b+c) (d+a) 

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

normalize (Int (S a) (S b)) = normalize (Int a b) 
normalize v = v