How do I parameterize a function by module in Haskell?

Question

This might seem artificial, but I can't seem to find an obvious answer to the following:

Say I have the following imports:

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

Now I have some function (comp) that takes some list, does something, creates a map, returns it.

My question is how do I have two ways of calling comp so that its calls (say) to insert and size map correctly?

As a strawman, I could write two copies of this function, one referencing M.insert and M.size, while the other references HML.insert and HML.size ... but how do I "pass the module as a parameter", or indicate this otherwise?

Thanks!

Edit: to make this less abstract these are the exact definitions of 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): this turned out to be way more interesting than I anticipated, thanks to everyone who responded!

Monopode

If I understand you correctly, I think you'd just have to pass some kind of parameter (either a Bool or some specially-constructed custom data type) to indicate which module you want to use. Perhaps others will know some more sophisticated way to do it. – Cristobalcristobalite

@RobinZigmond I see your point, you mean let insertfn = if <param> then M.insert else HML.insert (and similarly for sizefn) and then use insertfn as needed? I guess that works, but then I'm wondering whether there's an idiomatic way to do this when I have more than two possible modules. – Monopode

yes, that's what I meant. As I said, I don't know if there's a "nicer" way to do it - I don't think it's likely, but let's wait for the experts to comment/answer. – Cristobalcristobalite

Can't. A well designed typeclass interface often solves the same kind of problem, but not always. See also "backpack" which is an ML functor-like module extension for Haskell (still experimental, though I believe it's now shipping with ghc). – Duthie

Answer 1

Here's how to to it with module signatures and mixins (a.k.a. Backpack)

You would have to define a library (it could be an internal library) with a signature like:

-- 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

in the same library or in another, write code that imports the signature as if it were a normal module:

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 ()

In another library (it must be a different one) write an "implementation" module that matches the signature:

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

import Data.Map.Lazy

type C = Ord

The "signature match" is performed based on names and types only, the implementation module doesn't need to know about the existence of the signature.

Then, in a library or executable in which you want to use the abstract code, pull both the library with the abstract code and the library with the implementation:

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

Sometimes the name of the signature and of the implementing module don't match, in that case one has to use the mixins section of the Cabal file.

Edit. Creating the HashMap implementation proved somewhat tricky, because insert required two constraints (Eq and Hashable) instead of one. I had to resort to the "class synonym" trick. Here's the code:

{-# 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

Macintosh

Relevant links: kowainik.github.io/posts/… github.com/danidiaz/really-small-backpack-example – Macintosh

Excellent! Yeah, this seems like the "right" way to do this ... but is there a GHC version dependency here? (also, about the implementation example: there would be one of these per "concrete" module, correct? E.g. one for Data.Map and another for Data.Hashmap.Lazy ?) – Monopode

Nice. Since there's relatively little about backpack on this site, could you elaborate a little on when you might want to use this approach over something more traditional with typeclasses? IIUC think one of the benefits is you can offer users an API that is monomorphic but allow them to fiddle with the internals, e.g. replace the hashing algorithm in a hash-based containers library. Does that sound right? – Najera

@Monopode One needs a relatively recent version of GHC, an also a package manager that supports Backpack, which IIRC is only Cabal > 2.0 at the moment. Yes one needs one implementation per concrete module, although if some package with the right types and nomenclature already exists and matches your signature, you can simply use that (because implementations are independent of signatures). – Macintosh

@Najera Yes, Backpack seems useful to switch some internal detail in a module without complicating the function signatures and the definition of the datatypes. If you want to configure some aspect of your code that doesn't depend on runtime configuration and doesn't vary within your code (say, the type of string your library accepts) Backpack might be an option. But it has an overhead because you have to define all those auxiliary libraries, and it's not supported by all Haskell build systems. – Macintosh

I guess it's also a kind of looser coupling, since IIUC an implementation may incidentally match an interface; it doesn't need to be aware of the interface (in contrast to a library that must import/depend-on a typeclass). – Najera

Answer 2

The simplest is to parameterize by the operations you actually need, rather than the module. So:

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 ()

You can then call it as, e.g. mapComp M.empty M.insert M.size or mapComp HM.empty HM.insert HM.size. As a small side benefit, callers may use this function even if the data structure they prefer doesn't offer a module with exactly the right names and types by writing small adapters and passing them in.

If you like, you can combine these into a single record to ease passing them around:

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 ()

Fascicule

Thanks, the "passing a record of map ops" idea seems like the least bloat-y right now. – Monopode

Question: since I can't literally use K and V as in this example, I'm assuming you meant the underlying concrete types? i.e. if I "really" was using Data.Map String Int, I should annotate the type of insert as String -> Int -> m -> m ? (or, is there a way to say "the type of keys in the map of type m" ?) – Monopode

@Monopode Yes, use String and Int. You could alternately add additional parameters, as in data MapOps k v m = MapOps { insert :: k -> v -> m -> m, ... }. – Fascicule

@Monopode You could alternatively use a higher kinded m parameter, so that empty :: m k v, insert :: c k => k -> v -> m k v -> m k v, etc. Then you don't have to fix String and Int when you compile, or when you create a MapOps record, but you'll never be able to adapt a non-polymorphic map type, and you'll need to use ConstraintKinds to also add a c parameter for the constraint you need on the keys (e.g. Ord or Hashable). – Amalberga

@Amalberga That proposal makes the solution less flexible, not more. Even with insert :: k -> v -> m -> m you can make just one mapOps :: Ord k => MapOps (Map k v) k v without fixing the key and value type; but with your insert :: k -> v -> m k v -> m k v one can't use things like IntMap which take fewer type-level parameters (at least without newtype wrappers). – Fascicule

Answer 3

I'm a little suspicious this is an XY problem, so here's how I would address the code you linked to. You have, the following:

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 ()

This has a lot of repetition, which is usually not good. So we factor out the bits that are different between the two functions, and parameterize a new function by those changing bits:

-- 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 ()

As you can see this is a really mechanical process. Then you call e.g. comp M.empty M.insert M.size.

If you want to be able to define comp such that it can work on map types that you haven't thought of yet (or which your users will specify), then you must define comp against an abstract interface. This is done with typeclasses, as in SomeMap radrow's answer.

In fact you can do part of this abstracting already, by noticing that both maps you want to work with implement the standard Foldable and 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 ()

As mentioned in the comments, I think backpack is (will be?) the way to get what I think you're asking for, i.e. parameterized modules. I don't know much about it, and it's not clear to me what usecases it solves that you wouldn't want to use the more traditional approach I've described above (maybe I'll read the wiki page).

Najera

Answer 4

I am afraid that it is not possible to do in Haskell without workarounds. Main problem is that comp would use different types for same objects for M and for HML variants, which is impossible to do in Haskell directly.

You will need to let comp know which option are you going to take using either data or polymorphism.

As a base idea I would create ADT to cover possible options and use boolean value to determine the module:

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

And then use case expression in foldr to check whether your underlying map is M or HML. However, I don't see any good point of using such a bloatcode, it would be much better to create compM and compHML separately.

Another approach would be to create typeclass that would wrap all your cases

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

And then write instances for each map manually (or using some TemplateHaskell magic, which I believe could help here, however it is out of my skills). It will require some bloat code as well, but then you will be able to parametrize comp over the used map type:

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

But honestly, I would write this function like this:

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

Latoya