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

Лучший способ реализовать ad-hoc-полиморфизм в Haskell?

У меня есть полиморфная функция вроде:

convert :: (Show a) => a -> String
convert = " [label=" ++ (show a) ++ "]"

Но иногда я хочу передать ему Data.Map и сделать еще несколько модных значений. Я знаю, что здесь нет совпадения шаблонов, потому что Data.Map является абстрактным типом данных (в соответствии с похожим вопросом SO), но я не пользовался защитой от этого end, и я не уверен, что ViewPatterns поможет здесь (и скорее избежит их для переносимости).

Это больше я хочу:

import qualified Data.Map as M

convert :: (Show a) => a -> String
convert a 
    | M.size \=0 = processMap2FancyKVString a -- Heres a Data.Map
    | otherwise = " [label=" ++ (show a) ++ "]" -- Probably a string

Но это не работает, потому что M.size не может брать ничего, кроме Data.Map.

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

Обновление

Мне жаль, что я не смогу принять все три ответа TomMD, Antal S-Z и luqui на этот вопрос, поскольку все они понимали, что я действительно спрашивал. Я бы сказал:

  • Antal S-Z предоставил самое "элегантное" решение применительно к FGL, но также потребовало бы перезаписи и переосмысления для реализации в личной проблеме.
  • TomMD дал отличный ответ, который находится где-то между Antal S-Z и luqui с точки зрения применимости и правильности. Это также прямо и до такой степени, что я очень ценю и почему я выбрал его ответ.
  • luqui дал лучший ответ "быстро заработал", который я, вероятно, буду использовать на практике (поскольку я студент-градиент, и это всего лишь некоторый код для проверки некоторых идей). Причина, по которой я не соглашался, заключалась в том, что ответ TomMD, вероятно, поможет другим людям в более общих ситуациях лучше.

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

4b9b3361

ОТВЕТЫ

Ответ 1

Что вы только что объяснили - вам нужна функция, которая ведет себя по-разному в зависимости от типа ввода. Хотя вы можете использовать обертку data, тем самым закрывая эту функцию на все время:

data Convertable k a = ConvMap (Map k a) | ConvOther a
convert (ConvMap m) = ...
convert (ConvOther o) = ...

Лучше всего использовать классы типов, тем самым оставляя функцию convert открытой и расширяемой, не позволяя пользователям вводить нечувствительные комбинации (например: ConvOther M.empty).

class (Show a) => Convertable a where
    convert :: a -> String

instance Convertable (M.Map k a) where
    convert m = processMap2FancyKVString m

newtype ConvWrapper a = CW a
instance Convertable (ConvWrapper a) where
    convert (CW a) = " [label=" ++ (show a) ++ "]"

Таким образом, вы можете использовать экземпляры, которые вы хотите использовать для каждого типа данных, и каждый раз, когда вам нужна новая специализация, вы можете расширить определение convert просто добавив еще один instance Convertable NewDataType where ....

Некоторые люди могут нахмуриться в оболочке newtype и предложить экземпляр вроде:

instance Convertable a where
    convert ...

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

Ответ 2

Вы не можете задавать правильные вещи. Я предполагаю, что у вас либо есть граф, чьи узлы все Map, либо у вас есть граф, чьи узлы все что-то еще. Если вам нужен граф, где Map и не-карты сосуществуют, то есть еще к вашей проблеме (но это решение по-прежнему поможет). См. Конец моего ответа в этом случае.

Самый чистый ответ здесь - просто использовать разные функции convert для разных типов и иметь любой тип, который зависит от convert воспринимать его как аргумент (функция более высокого порядка).

Итак, в GraphViz (избегая перепроектирования этого дрянного кода) я бы изменил функцию graphviz, чтобы выглядеть так:

graphvizWithLabeler :: (a -> String) -> ... -> String
graphvizWithLabeler labeler ... =
   ...
   where sa = labeler a

И затем graphviz тривиально делегировать ему:

graphviz = graphvizWithLabeler sl

Затем graphviz продолжает работать по-прежнему, и у вас есть graphvizWithLabeler, когда вам нужна более мощная версия.

Итак, для графов, узлы которых Maps, используйте graphvizWithLabeler processMap2FancyKVString, иначе используйте graphviz. Это решение может быть отложено как можно дольше, принимая соответствующие вещи как функции более высокого порядка или методы типа.

Если вам нужно иметь Map и другие вещи, сосуществующие на одном и том же графике, тогда вам нужно найти один тип, в котором все, что может быть node. Это похоже на предложение TomMD. Например:

data NodeType
    = MapNode (Map.Map Foo Bar)
    | IntNode Int

Параметризирован на нужный уровень, который вам нужен, конечно. Тогда ваша функция метки должна решить, что делать в каждом из этих случаев.

Ключевым моментом, который следует помнить, является то, что у Haskell нет нисходящего потока. Функция типа foo :: a -> a не имеет возможности ничего знать о том, что было передано ему (в разумных пределах, охладите струйные педанты). Поэтому функцию, которую вы пытались написать, невозможно выразить в Haskell. Но, как вы можете видеть, есть другие способы сделать работу, и они оказываются более модульными.

Знаете ли вы, что вам нужно знать, чтобы выполнить то, что вы хотели?

Ответ 3

Ваша проблема на самом деле не такая, как в этом вопросе. В вопросе, с которым вы связались, у Дерека Терна была функция, которую он знал, взял Set a, но не смог сопоставить образ. В вашем случае вы пишете функцию, которая примет любой a, который имеет экземпляр Show; вы не можете определить, на какой тип вы смотрите во время выполнения, и можете полагаться только на функции, доступные для любого типа Show. Если вы хотите, чтобы функция выполняла разные вещи для разных типов данных, это называется ad-hoc-полиморфизмом и поддерживается в Haskell с типами классов типа Show. (Это в отличие от параметрического полиморфизма, когда вы пишете функцию типа head (x:_) = x, которая имеет тип head :: [a] -> a, а не неограниченный универсальный a - это то, что делает эту параметрику вместо этого.) Итак, чтобы делать то, что вы хотите, вам нужно создать свой собственный класс типа и создать его, когда вам это нужно. Однако это немного сложнее обычного, потому что вы хотите сделать все, что часть Show неявно является частью вашего нового типа. Для этого требуются некоторые потенциально опасные и, вероятно, излишне мощные расширения GHC. Вместо этого, почему бы не упростить вещи? Вероятно, вы можете найти подмножество типов, которые вам действительно нужно печатать таким образом. После этого вы можете написать код следующим образом:

{-# LANGUAGE TypeSynonymInstances #-}

module GraphvizTypeclass where

import qualified Data.Map as M
import Data.Map (Map)

import Data.List (intercalate) -- For output formatting

surround :: String -> String -> String -> String
surround before after = (before ++) . (++ after)

squareBrackets :: String -> String
squareBrackets = surround "[" "]"

quoted :: String -> String
quoted = let replace '"' = "\\\""
             replace c   = [c]
         in surround "\"" "\"" . concatMap replace

class GraphvizLabel a where
  toGVItem  :: a -> String
  toGVLabel :: a -> String
  toGVLabel = squareBrackets . ("label=" ++) . toGVItem

-- We only need to print Strings, Ints, Chars, and Maps.

instance GraphvizLabel String where
  toGVItem = quoted

instance GraphvizLabel Int where
  toGVItem = quoted . show

instance GraphvizLabel Char where
  toGVItem = toGVItem . (: []) -- Custom behavior: no single quotes.

instance (GraphvizLabel k, GraphvizLabel v) => GraphvizLabel (Map k v) where
  toGVItem  = let kvfn k v = ((toGVItem k ++ "=" ++ toGVItem v) :)
              in intercalate "," . M.foldWithKey kvfn []
  toGVLabel = squareBrackets . toGVItem

В этой настройке все, что мы можем выводить на Graphviz, является экземпляром GraphvizLabel; функция toGVItem цитирует вещи, а toGVLabel помещает все это в квадратные скобки для немедленного использования. (Я мог бы прикрутить некоторое форматирование, которое вы хотите, но эта часть просто пример.) Затем вы объявляете, что такое экземпляр GraphvizLabel, и как превратить его в элемент. Флаг TypeSynonymInstances позволяет нам писать instance GraphvizLabel String вместо instance GraphvizLabel [Char]; это безвредно.

Теперь, если вам действительно нужно все с экземпляром Show, чтобы быть экземпляром GraphvizLabel, есть способ. Если вам это действительно не нужно, не используйте этот код! Если вам нужно это сделать, вам нужно вывести условно-именные UndecidableInstances и OverlappingInstances языковые расширения (и менее scarily с именем FlexibleInstances). Причиной этого является то, что вы должны утверждать, что все, что Show доступно, - это GraphvizLabel, но это сложно компилятору рассказать. Например, если вы используете этот код и пишите toGVLabel [1,2,3] в приглашении GHCi, вы получите сообщение об ошибке, так как 1 имеет тип Num a => a, а Char может быть экземпляром Num! Вы должны явно указать toGVLabel ([1,2,3] :: [Int]), чтобы заставить его работать. Опять же, это, вероятно, излишне тяжелое оборудование, которое может повлиять на вашу проблему. Вместо этого, если вы можете ограничить то, что, по вашему мнению, будет преобразовано в ярлыки, что очень вероятно, вы можете просто указать эти вещи вместо этого! Но если вы действительно хотите, чтобы способность Show подразумевала способность GraphvizLabel, это то, что вам нужно:

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances
,          UndecidableInstances, OverlappingInstances #-}

-- Leave the module declaration, imports, formatting code, and class declaration
-- the same.

instance GraphvizLabel String where
  toGVItem = quoted

instance Show a => GraphvizLabel a where
  toGVItem = quoted . show

instance (GraphvizLabel k, GraphvizLabel v) => GraphvizLabel (Map k v) where
  toGVItem  = let kvfn k v = ((toGVItem k ++ "=" ++ toGVItem v) :)
              in intercalate "," . M.foldWithKey kvfn []
  toGVLabel = squareBrackets . toGVItem

Обратите внимание, что ваши конкретные случаи (GraphvizLabel String и GraphvizLabel (Map k v)) остаются неизменными; вы только что свернули случаи Int и Char в случай GraphvizLabel a. Помните, что UndecidableInstances означает именно то, что он говорит: компилятор не может определить, могут ли экземпляры проверяться или вместо этого сделать цикл typechecker! В этом случае я уверен, что все на самом деле разрешимо (но если кто-нибудь замечает, где я ошибаюсь, сообщите мне об этом). Тем не менее, использование UndecidableInstances должно всегда подходить с осторожностью.