Как мне параметризировать функцию по модулю в Haskell?

Question

Это может показаться искусственным, но я не могу найти очевидный ответ на следующие вопросы:

Скажем, у меня есть следующий импорт:

import qualified Data.Map as M
import qualified Data.HashMap.Lazy as HML

Теперь у меня есть какая-то функция (comp), которая берет какой-то список, что-то делает, создает карту, возвращает ее.

Мой вопрос заключается в том, как мне использовать два способа вызова comp, чтобы его вызовы (скажем) на insert и size отображались правильно?

Как соломенный человек, я мог бы написать две копии этой функции, одна из которых ссылается на M.insert и M.size, в то время как другие ссылки HML.insert и HML.size ... но как мне "передать модуль как параметр ", или указать это иначе?

Спасибо!

Редактировать: , чтобы сделать это менее абстрактным, это точные определения comp:

mapComp :: KVPairs -> IO ()
mapComp kvpairs = do
  let init = M.empty
  let m = foldr ins init kvpairs where
        ins (k, v) t = M.insert k v t
  if M.size m /= length kvpairs
  then putStrLn $ "FAIL: " ++ show (M.size m) ++ ", " ++ show (length kvpairs)
  else pure ()

hashmapComp :: KVPairs -> IO()
hashmapComp kvpairs = do
  let init = HML.empty
  let m = foldr ins init kvpairs where
        ins (k, v) t = HML.insert k v t
  if HML.size m /= length kvpairs
  then putStrLn $ "Fail: " ++ show (HML.size m) ++ ", " ++ show (length kvpairs)
  else pure ()

Edit (2): это оказалось способ интереснее, чем я ожидал, спасибо всем, кто откликнулся!

Answer 1

Вот как это сделать с помощью сигнатур модулей и миксинов (a.k.a. Backpack )

Вы должны определить библиотеку (это может быть внутренняя библиотека) с подписью , например:

-- file Mappy.hsig
signature Mappy where

class C k
data Map k v
empty :: Map k v
insert :: C k => k -> v -> Map k v -> Map k v 
size :: Map k v -> Int

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

module Stuff where

import qualified Mappy as M

type KVPairs k v = [(k,v)]

comp :: M.C k => KVPairs k v -> IO ()
comp kvpairs = do
  let init = M.empty
  let m = foldr ins init kvpairs where
        ins (k, v) t = M.insert k v t
  if M.size m /= length kvpairs
  then putStrLn $ "FAIL: " ++ show (M.size m) ++ ", " ++ show (length kvpairs)
  else pure ()

В другой библиотеке (она должна быть другой) напишите модуль «реализации», соответствующий сигнатуре:

-- file Mappy.hs
{-# language ConstraintKinds #-}
module Mappy (C,insert,empty,size,Map) where

import Data.Map.Lazy

type C = Ord

«Сопоставление подписи» выполняется только на основе имен и типов, модуль реализации не должен знать о существовании подписи.

Затем в библиотеке или исполняемом файле, в котором вы хотите использовать абстрактный код, вытащите и библиотеку с абстрактным кодом, и библиотеку с реализацией:

executable somexe
  main-is:             Main.hs
  build-depends:       base ^>=4.11.1.0,
                       indeflib,
                       lazyimpl
  default-language:    Haskell2010

library indeflib
  exposed-modules:     Stuff
  signatures:          Mappy
  build-depends:       base ^>=4.11.1.0
  hs-source-dirs:      src
  default-language:    Haskell2010

library lazyimpl
  exposed-modules:     Mappy
  build-depends:       base ^>=4.11.1.0,
                       containers >= 0.5
  hs-source-dirs:      impl1
  default-language:    Haskell2010

Иногда имя подписи и реализующего модуля не совпадают, в этом случае необходимо использовать раздел mixins файла Cabal.

Edit. Создание реализации HashMap оказалось несколько сложным, потому что insert требовало двух ограничений (Eq и Hashable) вместо одного. Мне пришлось прибегнуть к «синониму класса» . Вот код:

{-# language ConstraintKinds, FlexibleInstances, UndecidableInstances #-}
module Mappy (C,insert,HM.empty,HM.size,Map) where

import Data.Hashable
import qualified Data.HashMap.Strict as HM

type C = EqHash 

class (Eq q, Hashable q) => EqHash q -- class synonym trick
instance (Eq q, Hashable q) => EqHash q

insert :: EqHash k => k -> v -> Map k v -> Map k v
insert = HM.insert

type Map = HM.HashMap

Answer 2

Самым простым является параметризация по операциям, которые вам действительно нужны, а не по модулю. Итак:

mapComp ::
  m ->
  (K -> V -> m -> m) ->
  (m -> Int) ->
  KVPairs -> IO ()
mapComp empty insert size kvpairs = do
  let m = foldr ins empty kvpairs where
        ins (k, v) t = insert k v t
  if size m /= length kvpairs
  then putStrLn $ "FAIL: " ++ show (size m) ++ ", " ++ show (length kvpairs)
  else pure ()

Затем вы можете назвать это, например, mapComp M.empty M.insert M.size или mapComp HM.empty HM.insert HM.size. В качестве небольшого побочного преимущества вызывающие абоненты могут использовать эту функцию, даже если предпочитаемая им структура данных не предлагает модуль с точно правильными именами и типами, написав небольшие адаптеры и передав их.

Если хотите, вы можете объединить их в одну запись, чтобы облегчить их передачу:

data MapOps m = MapOps
    { empty :: m
    , insert :: K -> V -> m -> m
    , size :: m -> Int
    }

mops = MapOps M.empty M.insert M.size
hmops = MapOps HM.empty HM.insert HM.size

mapComp :: MapOps m -> KVPairs -> IO ()
mapComp ops kvpairs = do
    let m = foldr ins (empty ops) kvpairs where
          ins (k, v) t = insert ops k v t
    if size ops m /= length kvpairs
    then putStrLn "Yikes!"
    else pure ()

Answer 3

Я немного подозреваю, что это проблема XY, так что вот как бы я решил код, на который вы ссылались. У вас есть следующее:

mapComp :: KVPairs -> IO ()
mapComp kvpairs = do
  let init = M.empty
  let m = foldr ins init kvpairs where
        ins (k, v) t = M.insert k v t
  if M.size m /= length kvpairs
  then putStrLn $ "FAIL: " ++ show (M.size m) ++ ", " ++ show (length kvpairs)
  else pure ()

hashmapComp :: KVPairs -> IO()
hashmapComp kvpairs = do
  let init = HML.empty
  let m = foldr ins init kvpairs where
        ins (k, v) t = HML.insert k v t
  if HML.size m /= length kvpairs
  then putStrLn $ "Fail: " ++ show (HML.size m) ++ ", " ++ show (length kvpairs)
else pure ()

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

-- didn't try to compile this
comp :: mp k v -> (k -> v -> mp k v -> mp k v) -> (mp k v -> Int) -> KVPairs -> IO()
comp h_empty h_insert h_size kvpairs = do
  let init = h_empty
  let m = foldr ins init kvpairs where
        ins (k, v) t = h_insert k v t
  if h_size m /= length kvpairs
  then putStrLn $ "Fail: " ++ show (h_size m) ++ ", " ++ show (length kvpairs)
else pure ()

Как видите, это действительно механический процесс. Тогда вы звоните, например, comp M.empty M.insert M.size.

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

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

-- didn't try to compile this
comp :: (Foldable (mp k), Monoid (mp k v))=> (k -> v -> mp k v -> mp k v) -> KVPairs -> IO()
comp h_insert kvpairs = do
  let init = mempty -- ...also why not just use `mempty` directly below:
  let m = foldr ins init kvpairs where
        ins (k, v) t = h_insert k v t
  if length m /= length kvpairs
  then putStrLn $ "Fail: " ++ show (length m) ++ ", " ++ show (length kvpairs)
else pure ()

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

Answer 4

Боюсь, что в Хаскеле невозможно обойтись без обходных путей. Основная проблема заключается в том, что comp будет использовать разные типы для одних и тех же объектов для M и для HML вариантов, что невозможно сделать непосредственно в Haskell.

Вам необходимо сообщить comp, какой вариант вы собираетесь использовать, используя данные или полиморфизм.

В качестве базовой идеи я бы создал ADT для покрытия возможных параметров и использовал бы логическое значение для определения модуля:

data SomeMap k v = M (M.Map k v) | HML (HML.HashMap k v)
f :: Bool -> IO ()
f shouldIUseM = do ...

А затем используйте выражение case в foldr, чтобы проверить, является ли ваша базовая карта M или HML. Тем не менее, я не вижу смысла использовать такой код, потому что было бы гораздо лучше создать compM и compHML отдельно.

Другим подходом было бы создание класса типов, который бы охватил все ваши дела

class SomeMap m where
  empty :: m k v
  insert :: k -> v -> m k v -> m k v
  size :: m k v -> Int

А затем напишите экземпляры для каждой карты вручную (или используя магию TemplateHaskell, которая, как я считаю, могла бы здесь помочь, однако это не в моих навыках). Это также потребует некоторого раздувного кода, но тогда вы сможете параметризовать comp по используемому типу карты:

comp :: SomeMap m => m -> IO ()
comp thisCouldBeEmptyInitMap = do ...

Но, честно говоря, я написал бы эту функцию так:

comp :: Bool -> IO ()
comp m = if m then fooM else fooHML