Подтвердить что ты не робот

Сравнение функций в Haskell

Есть ли способ сравнить две функции в Haskell?

Моя мысль заключается в том, что ответ отрицательный, поскольку функции не получат класс типа Eq. Однако я пытаюсь написать довольно тривиальную функцию, и это похоже на обычную вещь:

search :: ((Enum a) => a -> a) -> Card -> [Card]
search op x list = if (op == succ && rank x == King) || 
                      (op == pred && rank x == Ace)
                   then []
                   else let c = [ n | n <- list, rank n == op (rank x)]
                     in if length c == 1
                     then x : search op (head c) list
                     else []

Сообщение об ошибке:

No instance for (Eq (Rank -> Rank))
      arising from a use of `=='

В основном он либо ищет вверх или вниз список карт, которые ищут совпадение с следующей или предыдущей ранжированной картой от x, создавая список. Принимая функцию "pred" или "succ" в качестве оператора, он работает как вперед, так и назад. Тем не менее, мне нужно проверить, что он не выходит за пределы перечисления, иначе он выдает исключение.

Итак, я ищу способ предотвратить исключение или решить эту проблему!

Любые другие указатели на улучшение кода также будут оценены:)

Спасибо за все замечательные советы, это решение, которое я придумал (взятые бит от каждого ответа действительно!):

EDIT: Правильное решение ниже:

 maybeSucc x | x == maxBound = Nothing
             | otherwise = Just (succ x)
 maybePred x | x == minBound = Nothing  
             | otherwise = Just (pred x)

-- takes a list of cards which have a rank one op than x
-- only if there is exactly one is it sequential, otherwise end matching
search :: (Rank -> Maybe Rank) -> Rank -> [Card] -> [Card]
search op x list = case filter (\n -> Just (rank n) == op x) list of
                    [y] -> y : search op (rank y) list
                     _ -> []

Тест:

*Main> let cards = [Card Ace Heart, Card Two Club, Card Three Spade, Card Five Club, Card Four Diamond]

*Main> search maybeSucc Two cards

[Three of Spades,Four of Diamonds,Five of Clubs]

*Main> search maybePred Three cards

[Two of Clubs,Ace of Hearts]
4b9b3361

ОТВЕТЫ

Ответ 1

1) Ваш op слишком общий. Вы будете использовать его только для Card любого типа rank (undefined :: Card), поэтому просто сделайте его RankThing -> RankThing. Кроме того, в вашей сигнатуре типа функции отсутствует тип возвращаемого значения.

2) Пример предполагаемого использования выглядит так: search succ Ace xs, но это довольно неуклюжий, как насчет двух вспомогательных функций, которые обрабатывают границы:

searchUp King _ = []
searchUp x ys = search succ x ys

searchDown Ace _ = []
searchDown x ys = search pred x ys

Это может показаться лучше для ваших пользователей и избежать необходимости проверять работу

3), если вы действительно хотите проверить, какая операция выполнена, и знаете, что операция будет одной из двух возможностей, вы можете либо назвать операцию, либо проверить ее с помощью известного теста ответа (KAT). Например:

data Operation = Succ | Pred

search :: Operation -> Card -> [Card] -> []
search Succ King _ = []
search Succ x ys = search' succ x ys
search Pred Ace _ = []
search Pred x ys = search' pred x ys

И решение KAT (довольно хромое, imo):

search op x ys
    | op Five == Four && rank x == Ace = []
    | op Five == Six && rank x == King = []
    | otherwise = ...

Ответ 2

Неполный ответ

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

"Прагматичные" подходы будут либо зависеть от внутренних действий вашего компилятора (например, если две функции равны, если они представлены одним и тем же адресом памяти внутри) или менее полезны, чем ожидалось. Каков ожидаемый результат succ == (+1)? Как насчет let a == 1 в succ == (+ a)?

Я не могу придумать способ определения (==) для функций, которые всегда имеют смысл, и я не верю никому другому.

Вещи, не имеющие отношения к Вопросу

В сигнатуре типа отсутствует возвращаемый тип.

Ваша функция имеет тип ранга 2, который не является стандартным Haskell 98 и, что более важно, в этом случае не нужен. Вам все равно, может ли переданная функция работать с любым типом Enum, вам все равно, что она работает для Rank:

search :: (Rank -> Rank) -> Card -> [Card] -> [Card]   -- much simpler.

Я попытался бы использовать случай чаще, а если/то реже. В частности, я бы написал:

case [ n | n <- list, rank n == op (rank x)] of
    [y] -> x : search op y list   -- length == 1
    _ -> []                       -- otherwise

Мой реальный ответ

Ваша функция в основном работает только с двумя разными значениями для op, но ее тип не говорит об этом; что мне не подходит.

Вы можете сделать это старомодно:

data Direction = Succ | Pred deriving(Eq)

search :: Direction -> Card -> [Card] -> [Card]
search dir x list = if (dir == Succ && rank x == King) ...
    ... let op = case Direction of Succ -> succ ; Pred -> pred
        in ...

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

maybeSucc x | x == maxBound = Nothing
            | otherwise = Just (succ x)

search :: (Rank -> Maybe Rank) -> Card -> [Card] -> [Card]
search op x list = case op (rank x) of
    Nothing -> []
    Just theRank -> case [ n | n <- list, rank n == theRank ] of ...

Ответ 3

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

Существуют различные способы достижения вашей непосредственной цели, такие как:

  • Вместо прямого использования succ и pred используйте функции самозащиты с типом Enum a => a -> Maybe a, которые производят Nothing, а не исключение.

  • Перейдите в значение "stop", чтобы проверить, например, search op end x list = if x == end then [] ....

  • Забудьте о succ и pred целиком и просто перейдите в список значений для сравнения, например. search :: [Rank] -> Card -> [Card] -> [Card] и завершите поиск, если список рангов пуст.

Еще несколько замечаний по вашему коду:

  • Ваше понимание списка - изобретать колесо - искать стандартные библиотечные функции, такие как filter, которые будут делать то, что вы хотите.

  • Не сравнивайте length списка с небольшим сопоставлением шаблонов с использованием констант.

Ответ 4

Пока функции находятся над соответствующими доменами и диапазонами (Enum, Bounded, Eq и т.д., в несколько иной комбинации для домена и диапазона), вы можете сравнивать конечные функции, даже более высокие, вперед, а затем автоматизировать процесс с использованием классов типов.

Я написал эту идею в сообщении в один из списков рассылки Haskell, а затем (более правильно) в документе который я представил на одна из конференций FDPE (Виктория, Британская Колумбия). Я никогда не видел, чтобы это делалось раньше, но я не удивлюсь, если другие тоже это сделают: это довольно простая идея, как только вы преодолеете bugaboo, что "функции нельзя сравнивать для равенства" . Разумеется, применяются обычные оговорки относительно пристрастности и строгости: например, вы не можете вернуть True для двух функций, которые оба не могут прервать какой-либо общий аргумент.

Но для конечных областей эта техника работает и обеспечивает много практического использования. (Плюс это действительно просто интересно использовать:)).

Изменить: я добавил код hpaste здесь; он работает в Hugs, но нуждается в некоторых настройках для GHC.

Изменить 2: я добавил прагму и комментарий к hpaste-d-коду, чтобы он работал как в GHC, так и в Hugs. Я также добавил этот пример как test3 (он возвращает True, как и ожидалось, и в коротком порядке):

(\x -> [(&&x), (||x), not]) == (\y -> [(y&&), (y||), not . not . not])

Ответ 5

Код ниже не может компилироваться, но, надеюсь, вы получите идею:

data Op = Succ | Pred deriving Eq

fromOp :: Enum a => Op -> a -> a
fromOp Succ = succ
fromOp Pred = pred

search :: Op -> Card -> [Card] -> [Card]
search op x list = if (op == Succ && rank x == King) || 
                      (op == Pred && rank x == Ace)
                   then []
                   else let c = [ n | n <- list, rank n == (fromOp op) (rank x)]
                     in if length c == 1
                     then x : search op (head c) list
                     else []