没有Monad实例的“Data.Map”,但是Scala的地图？

trait Map[A,B+] extends Iterable[(A,B)] {
  def flatMap[B](f: (A) ? GenTraversableOnce[B]): Map[B]
}

它需要一对键值对映射(因为flatMap来自Iterable,其中A是(A,B))：

scala> val m = Map("one" -> 1,"two" -> 2)
m: scala.collection.immutable.Map[String,Int] = Map(one -> 1,two -> 2)

scala> m.flatMap (p => p match { case (_,v) => List(v,v + 3) })
res1: scala.collection.immutable.Iterable[Int] = List(1,4,2,5)

这不是monadic bind,它更接近Foldable的foldMap

λ > import Data.Map
λ > import Data.Monoid
λ > import Data.Foldable
λ > let m = fromList [("one",1),("two",2)]
λ > (v -> [v,v + 3]) `foldMap` m
[1,5]

地图是合法的Ord k => Apply (Map k v)和Ord k => Bind (Map k v)：

-- | A Map is not 'Applicative',but it is an instance of 'Apply'
instance Ord k => Apply (Map k) where
  (<.>) = Map.intersectionWith id
  (<. ) = Map.intersectionWith const
  ( .>) = Map.intersectionWith (const id)

-- | A 'Map' is not a 'Monad',but it is an instance of 'Bind'
instance Ord k => Bind (Map k) where
  m >>- f = Map.mapMaybeWithKey (k -> Map.lookup k . f) m

这有点像ZipList实例,可以按键拉链元素.注意：ZipList不是Bind(仅适用),因为您无法从范围之间删除元素.

并且你不能使它成为Applicative或Monad,因为没有办法让合法的纯/返回,它应该在所有键上都有一个值.或者,如果某些有限类型类约束k(因为Map在其脊椎中是严格的,因此您无法创建无限映射).

编辑：在评论中指出.如果我们正确思考,上面试图对MaybeT(读者k)v = k – >进行具体的(可检查的)表示.也许v与Map k v.但我们失败了,因为我们不能代表纯x = const x.但我们可以通过明确表示这种情况来尝试这样做：

module MMap (main) where

import Data.Map (Map)
import qualified Data.Map as Map
import Test.QuickCheck
import Test.QuickCheck.Function

import Control.Applicative
import Control.Monad

-- [[ MMap k v ]] ? k -> Maybe v 
data MMap k v = MConstant v
              | MPartial (Map k v)
  deriving (Eq,Ord,Show)

-- Morphism
lookup :: Ord k => k -> MMap k v -> Maybe v
lookup _ (MConstant x) = Just x
lookup k (MPartial m)  = Map.lookup k m

instance Functor (MMap k) where
  fmap f (MConstant v) = MConstant (f v)
  fmap f (MPartial m)  = MPartial (fmap f m)

instance Ord k => Applicative (MMap k) where
  pure = MConstant
  (MConstant f) <*> (MConstant x) = MConstant (f x)
  (MConstant f) <*> (MPartial x)  = MPartial (fmap f x)
  (MPartial f)  <*> (MConstant x) = MPartial (fmap ($x) f)
  (MPartial f)  <*> (MPartial x)  = MPartial (Map.intersectionWith ($) f x)

instance Ord k => Monad (MMap k) where
  return = MConstant
  (MConstant x) >>= f = f x
  (MPartial m) >>= f  = MPartial $Map.mapMaybeWithKey (k -> MMap.lookup k . f) m

instance (Ord k,Arbitrary k,Arbitrary v) => Arbitrary (MMap k v) where
  arbitrary = oneof [ MConstant <$> arbitrary,MPartial . Map.fromList <$> arbitrary
                    ]

prop1 :: Int -> Fun Int (MMap Int Int) -> Property
prop1 x (Fun _ f) = (return x >>= f) === f x

prop2 :: MMap Int Int -> Property
prop2 x = (x >>= return) === x

prop3 :: MMap Int Int -> Fun Int (MMap Int Int) -> Fun Int (MMap Int Int) -> Property
prop3 m (Fun _ f) (Fun _ g) = ((m >>= f) >>= g) === (m >>= (x -> f x >>= g))

main :: IO ()
main = do
  quickCheck prop1
  quickCheck prop2
  quickCheck prop3

确实有效！然而这个有点可疑的定义,因为我们无法定义语义正确的Eq实例：

m1 = MConstant 'a'
m2 = MPartial (Map.fromList [(True,'a'),(False,'a')])

m1是m2在语义上是等价的(查找k具有相同的结果),但结构上不同.而且我们无法知道MPartial何时定义了所有键值.

Spine指的是,呃,数据结构脊柱.例如,列表定义为

data List a = Nil | Cons a (List a)

脊柱不严格,但是

data SList a = SNil | SCons a !(SList a)

是.

您可以定义无限列表,但SList：

λ Prelude > let l = Cons 'a' l
λ Prelude > let sl = SCons 'a' sl
λ Prelude > l `seq` ()
()
λ Prelude > sl `seq` () -- goes into infinite loop

如Map is also strict in it’s spine

data Map k a  = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
              | Tip

我们无法构造无限的Map,即使我们有获得k类型的所有值的手段.但是我们可以构造无限的普通Haskell列表：[]为Applicative ZipList制作纯粹的.