Haskell中的OCaml仿函数(参数化模块)仿真

Question

是否有任何推荐的方法来使用类型类来模拟类似OCaml的参数化模块？

例如,我需要实现复杂泛型计算的模块,可以用不同的misc进行分解.更具体地说,让它成为kMeans实现,可以使用不同类型的值,矢量类型(列表,未装箱的矢量,矢量,元组等)和距离计算策略进行参数化.

为方便起见,为了避免疯狂数量的中间类型,我希望DataSet类具有多态性,包含所有必需的接口.我还尝试使用TypeFamilies来避免大量的类型参数(这也导致了问题):

{-# Language MultiParamTypeClasses
           , TypeFamilies
           , FlexibleContexts
           , FlexibleInstances
           , EmptyDataDecls
           , FunctionalDependencies
           #-}

module Main where

import qualified Data.List as L
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as U

import Distances
-- contains instances for Euclid distance
-- import Distances.Euclid as E
-- contains instances for Kulback-Leibler "distance"
-- import Distances.Kullback as K

class ( Num (Elem c)
     ,  Ord (TLabel c)
     ,  WithDistance (TVect c) (Elem c)
     ,  WithDistance  (TBoxType c) (Elem c)
     ) 
     => DataSet c  where
    type Elem c  ::  *
    type TLabel c ::  *
    type TVect c :: * -> *
    data TDistType  c :: *
    data TObservation c :: *
    data TBoxType c :: * -> *
    observations :: c -> [TObservation c]
    measurements :: TObservation c -> [Elem c]
    label        :: TObservation c -> TLabel c
    distance :: TBoxType c (Elem c) -> TBoxType c (Elem c) -> Elem c
    distance = distance_

instance DataSet () where
  type Elem () = Float
  type TLabel () = Int
  data TObservation () = TObservationUnit [Float]
  data TDistType ()
  type TVect () = V.Vector 
  data TBoxType () v = VectorBox (V.Vector v)
  observations () = replicate 10 (TObservationUnit [0,0,0,0])
  measurements (TObservationUnit xs) = xs
  label (TObservationUnit _) = 111 

kMeans :: ( Floating (Elem c)
          , DataSet c
          ) => c
            -> [TObservation c]
kMeans s = undefined -- here the implementation
  where
    labels = map label (observations s)
    www  = L.map (V.fromList.measurements) (observations s)
    zzz  = L.zipWith distance_ www www
    wtf1 = L.foldl wtf2 0 (observations s)
    wtf2 acc xs = acc + L.sum (measurements xs)
    qq = V.fromList [1,2,3 :: Float]
    l = distance (VectorBox qq) (VectorBox qq)

instance Floating a => WithDistance (TBoxType ()) a where
  distance_ xs ys = undefined

instance Floating a => WithDistance V.Vector a where
  distance_  xs ys = sqrt $ V.sum (V.zipWith (\x y -> (x+y)**2) xs ys)

这段代码以某种方式编译和工作,但它非常丑陋和hacky.

kMeans应该通过值类型(数字,浮点数,任何东西),框类型(向量,列表,未装箱的向量,可能是元组)和距离计算策略进行参数化.

观察也有类型(这是用户提供的样本类型,应该有很多类型,每个观察中包含的测量值).

所以问题是:

1)如果函数不包含其签名中的参数类型,则不会推导出类型

2)仍然不知道,如何声明类型类WithDistance为不同的距离类型(Euclid,Kullback,其他任何通过幻像类型)的不同实例.

现在WithDistance只是盒子类型和值类型的多态,所以如果我们需要不同的策略,我们可能只将它们放在不同的模块中并导入所需的模块.但这是一种黑客和非打字的方法,对吧？

所有这些都可以在OCaml中使用is't模块完成.在Haskell中实现这些东西的正确方法是什么？

具有TypeFamilies的类型类似于参数模块,但它们的工作方式不同.我真的需要这样的东西.

Answer 1

事实上,Haskell缺乏*ML模块系统中的有用功能.
正在不断努力扩展Haskell的模块系统:http://plv.mpi-sws.org/backpack/

但我认为如果没有那些ML模块,你可以得到更多.你的设计遵循上帝的反模式,这就是为什么它是反模块化的.

仅当每个类型只能包含该类的单个实例时,类型类才有用.例如DataSet ()实例修复type TVect () = V.Vector,你不能轻易创建类似的实例,但有TVect = U.Vector.

您需要从实现kMeans函数开始,然后通过使用类型变量替换具体类型并在需要时使用类型约束这些类​​型变量来对其进行概括.

这是一个小例子.首先,你有一些非一般的实现:

kMeans :: Int -> [(Double,Double)] -> [[(Double,Double)]]
kMeans k points = ...

然后通过距离计算策略对其进行概括:

kMeans
   :: Int
   -> ((Double,Double) -> (Double,Double) -> Double)
   -> [(Double,Double)]
   -> [[(Double,Double)]]
kMeans k distance points = ...

现在你可以按点的类型来概括它,但这需要引入一个类来捕获距离计算所使用的点的一些属性,例如获取坐标列表:

kMeans
    :: Point p
    => Int -> (p -> p -> Coord p) -> [p]
    -> [[p]]
kMeans k distance points = ...

class Num (Coord p) => Point p where
    type Coord p
    coords :: p -> [Coord p]

euclidianDistance
    :: (Point p, Floating (Coord p))
    => p -> p -> Coord p
euclidianDistance a b
    = sum $ map (**2) $ zipWith (-) (coords a) (coords b)

现在,您可能希望通过使用向量替换列表来加快速度:

kMeans
    :: (Point p, DataSet vec p)
    => Int -> (p -> p -> Coord p) -> vec p
    -> [vec p]
kMeans k distance points = ...

class DataSet vec p where
  map :: ...
  foldl' :: ...

instance Unbox p => DataSet U.Vector p where
  map = U.map
  foldl' = U.foldl'

等等.

建议的方法是概括算法的各个部分,并用小松散耦合类型约束那些部分(如果需要).
在单个整体类型类中收集所有内容是一种糟糕的风格.