Как выразить сопоставление с образцом для независимых комбинаций значений данных?

data Foo = Bar1
         | Bar2 Foo Foo
         | Bar3 Foo
         | Bar4 Foo Foo Foo

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

  • Bar2 Bar1 Foo
  • Bar3 (Bar2|Bar3|Bar4)
  • Bar4 Bar1 Bar1 (Bar1|Bar4)

Я знаю конструктор значения и хочу проверить только непосредственные аргументы, ничего рекурсивного. Нравится:

bar2 Bar1 Bar1      = True
bar2 Bar1 (Bar2 {}) = True
bar2 Bar1 (Bar3 _)  = True
bar2 Bar1 (Bar4 {}) = True
bar2 _ _ = False

И например. аналогично для Bar4:

bar4 Bar1 Bar1 Bar1      = True
bar4 Bar1 Bar1 (Bar4 {}) = True
bar4 _ _ _ = False

Как я могу выразить эти условия наиболее кратко? Перечисление всех комбинаций в некоторых случаях слишком много. Насколько мне известно, синтаксиса «ИЛИ» для сопоставления с образцом не существует.

ОБНОВИТЬ

Я адаптировал решение Даниэля и пришел к этому:

data Foo = Bar1
         | Bar2 Foo Foo
         | Bar3 Foo
         | Bar4 Foo Foo Foo
         deriving (Data, Typeable)

bar2 a b = a `isOf` [Bar1] && b `isOf` [Bar1,Bar2{},Bar3{},Bar4{}]
bar4 a b c = [a,b] `areOf` [Bar1] && c `isOf` [Bar1,Bar4{}]

isOf l r = toConstr l `elem` map toConstr r
areOf l r = all (`isOf` r) l

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


generic-programming haskell pattern-matching gadt
person letmaik    schedule 17.08.2012    source источник
comment
Являются ли эти комбинации единственным допустимым использованием Bar2, Bar3 и Bar4? (Т.е. проверяют ли условия, что они легальны.) Если это так, то, вероятно, лучше попытаться закодировать условия в системе типов, чтобы не было возможности их сломать.   -  person huon    schedule 17.08.2012
comment
Да, я тоже думал о том, чтобы сделать это с типами. Но мои попытки пока не увенчались успехом. Я попробовал это с GADT.   -  person letmaik    schedule 17.08.2012
comment
Просто примечание: вы можете упростить шаблон для Bar2 как bar2 Bar1 _ = True.   -  person Petr    schedule 17.08.2012
comment
Чего мне действительно не хватает, так это чего-то вроде instanceof в Java, тогда я мог бы, по крайней мере, сделать это с некоторыми вложенными if'ами. Я думаю, что эквивалент с case..of немного неудобен в Haskell для этого конкретного случая.   -  person letmaik    schedule 17.08.2012
comment
@нео, правда? Я думаю, что bar4 Bar1 Bar1 a = case a of Bar1 -> True; Bar4 {} -> True; _ -> False лучше, чем совпадение повторяющегося шаблона.   -  person huon    schedule 17.08.2012

Ответы (2)


arrow_upward
2
arrow_downward

Опубликовано прекрасное решение для статической проверки; вот предложение для решения динамической проверки. Основная идея состоит в том, чтобы избегать сопоставления с образцом и вместо этого использовать все имеющиеся у нас инструменты для написания компактного кода. Для этого есть несколько вариантов; Я расскажу о двух. Первый — написать isBarX функций для каждого конструктора:

isBar1 (Bar1 {}) = True
isBar1 _ = False

-- ...

isBar4 (Bar4 {}) = True
isBar4 _ = False

valid (Bar1)       = True
valid (Bar2 a b)   = isBar1 a
valid (Bar3 a)     = not (isBar1 a)
valid (Bar4 a b c) = isBar1 a && isBar1 b && (isBar1 c || isBar4 c)

Другой вариант — написать функцию, которая возвращает некоторые данные, говорящие о том, какой конструктор использовался — скажем, пользовательский тип, такой как data Constructor = CBar1 | CBar2 | CBar3 | CBar4, или, как я сделаю ниже, что-то более хакерское, например Int.

constr (Bar1 {}) = 1
constr (Bar2 {}) = 2
constr (Bar3 {}) = 3
constr (Bar4 {}) = 4

valid (Bar1)       = True
valid (Bar2 a b)   = constr a == 1
valid (Bar3 a)     = constr a /= 1
valid (Bar4 a b c) = constr a == 1 && constr b == 1 && constr c `elem` [1,4]
person Daniel Wagner    schedule 17.08.2012
comment
Первое решение, вероятно, самое простое, но я немного сомневаюсь в создании дополнительных функций is*. Что касается второго решения, можно ли это сделать с помощью Constr из Data.Data? Или печатаемый? Я еще не сталкивался с этими двумя вещами. - person letmaik; 17.08.2012
comment
@neo Да, deriving Typeable по сути пишет эти функции для вас, хорошая мысль! - person Daniel Wagner; 18.08.2012
comment
Хм, я не уверен, что Typeable действительно сильно помогает здесь. Я всегда могу преобразовать значение в Constr, но как мне сравнить его с самоопределяемым Constr? нравится valid (Bar2 a b) = toConstr a == ?? - person letmaik; 18.08.2012
comment
Ха-ха, плохой пример! :D как насчет valid (Bar4 a b c) = toConstr a == toConstr Bar1 && toConstr b == toConstr Bar1 && toConstr c elem [??] - person letmaik; 18.08.2012
comment
@neo Это не сильно другой пример, не так ли? Только 1_. - person Daniel Wagner; 18.08.2012
comment
Черт, ты прав! Почему-то у меня сложилось впечатление, что я не могу построить значения данных без всех параметров. Но тогда частичное строительство тоже не сработает... - person letmaik; 18.08.2012

arrow_upward
5
arrow_downward

Я думаю, что единственный способ проверить это на уровне системы типов — разделить его на несколько типов данных. Что-то типа:

data Foo = Foo1 Bar1 | Foo2 Bar2 | Foo3 Bar3 | Foo4 Bar4
data Bar1 = Bar1
data Bar2 = Bar2a Bar1 Foo
data Bar3 = Bar3a Bar2 | Bar3b Bar3 | Bar3c Bar4
data Bar4 = Bar4a Bar1 Bar1 Bar1 | Bar4b Bar1 Bar1 Bar4

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

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

Редактировать. Возможно, другим решением было бы использование фантомного типа для пометки конструкторов с помощью GADT:

{-# LANGUAGE GADTs #-}

data FBar1
data FBar2
data FBar3
data FBar4

data Foo a where
    Bar1 :: Foo FBar1
    Bar2 :: Foo FBar1 -> Foo b -> Foo FBar2
    Bar3a :: Foo FBar2 -> Foo FBar3
    Bar3b :: Foo FBar3 -> Foo FBar3
    Bar3c :: Foo FBar4 -> Foo FBar3
    Bar4a :: Foo FBar1 -> Foo FBar1 -> Foo FBar4
    Bar4b :: Foo FBar1 -> Foo FBar4 -> Foo FBar4

Я не уверен, что это решение не создаст больше проблем, чем решит. Например, невозможно написать такую ​​функцию:

construct :: Int -> FooAny X
construct 0 = Bar1
construct 1 = Bar2 Bar1 Bar1

поскольку X должно быть и FBar1, и FBar2. Для этого вам понадобятся экзистенциалы, например, чтобы обернуть его как

data FooAny where
    FooAny :: Foo a -> FooAny

construct :: Int -> FooAny
construct 0 = FooAny $ Bar1
construct 1 = FooAny $ Bar2 Bar1 Bar1
person Petr    schedule 17.08.2012
comment
Хм, я тоже думал об этом однажды, но, к сожалению, мне нужен один рекурсивный тип данных, и я не могу его разделить. - person letmaik; 17.08.2012