Haskell 新手类型

Question

我对 Haskell 完全陌生(更普遍的是函数式编程)，所以如果这真的是基本的东西，请原谅我。为了获得更多的体验，我尝试在 Haskell 中实现一些我正在研究的算法。我有一个简单的模块 Interval实现就行的间隔。它包含类型

data Interval t = Interval t t

辅助函数

makeInterval :: (Ord t) => t -> t -> Interval t  
makeInterval l r  | l <= r    = Interval l r  
                  | otherwise = error "bad interval"  

以及一些关于区间的实用函数。

在这里，我的兴趣在于多维区间(d 区间)，即由 d 区间组成的那些对象。我想分别考虑 d 间隔，它是线上 d 个不相交间隔的并集(多个间隔)与 d 条独立线上的 d 间隔的并集(轨道间隔)。考虑到不同的算法处理，我认为最好有两种不同的类型(即使两者都是这里的区间列表)，例如

import qualified Interval as I

-- Multilple interval  
newtype MInterval t = MInterval [I.Interval t]  

   -- Track interval  
newtype TInterval t = TInterval [I.Interval t]    

允许进行不同的健全性检查，例如

makeMInterval :: (Ord t) => [I.Interval t] -> MInterval t
makeMInterval is = if foldr (&&) True [I.precedes i i' | (i, i') <- zip is (tail is)]  
                   then (MInterval is)
                   else error "bad multiple interval"


makeTInterval :: (Ord t) => [I.Interval t] -> TInterval t
makeTInterval  = TInterval 

我现在进入正题，终于!但是有些函数自然会同时关注多个区间和轨道区间。例如，函数 order将返回多个间隔或跟踪间隔中的间隔数。我能做些什么？添加

-- Dimensional interval
data DInterval t = MIntervalStuff (MInterval t) | TIntervalStuff (TInterval t)

没有多大帮助，因为如果我理解得很好(如果我错了，请纠正我)，我将不得不写

order :: DInterval t -> Int
order (MIntervalStuff (MInterval is)) = length is
order (TIntervalStuff (TInterval is)) = length is

并调用order如order (MIntervalStuff is)或 order (TIntervalStuff is)当is是 MInterval或 TInterval .不是很好，看起来很奇怪。我也不想复制这个函数(我有很多函数都与多重和轨道间隔有关，以及其他一些 d 间隔定义，例如等长多重和轨道间隔)。

我觉得我完全错了，错过了一些关于 Haskell 类型的重要观点(和/或在这里不能忘记关于 OO 编程的足够多的内容)。所以，一个相当新手的问题，在 Haskell 中处理这种情况的最佳方法是什么？我必须忘记介绍MInterval吗？和 TInterval只选择一种类型？

非常感谢你的帮助，

加鲁尔福

Answer 1

编辑:这与 sclv 的答案相同；他的链接提供了有关此技术的更多信息。

这种方法怎么样？

data MInterval = MInterval --multiple interval
data TInterval = TInterval --track interval

data DInterval s t = DInterval [I.Interval t]

makeMInterval :: (Ord t) => [I.Interval t] -> Maybe (DInterval MInterval t)
makeMInterval is = if foldr (&&) True [I.precedes i i' | (i, i') <- zip is (tail is)]
  then Just (DInterval is)
  else Nothing

order :: DInterval s t -> Int
order (DInterval is) = length is

equalOrder :: DInterval s1 t -> DInterval s2 t -> Bool
equalOrder i1 i2 = order i1 == order i2

addToMInterval :: DInterval MInterval t -> Interval t -> Maybe (DInterval MInterval t)
addToMInterval = ..

这里类型 DInterval 表示多维区间，但它需要一个额外的类型参数作为幻像类型。这个额外的类型信息允许类型检查器区分不同类型的间隔，即使它们具有完全相同的表示。

您获得了原始设计的类型安全性，但您的所有结构都共享相同的实现。至关重要的是，当间隔的类型无关紧要时，您可以不指定它。

我还更改了您的 makeMInterval 函数的实现；返回 Maybe对于这样的函数，比调用错误更惯用。

关于可能的更多解释:

让我们检查一下你的函数 makeInterval .这个函数应该获取一个间隔列表，如果它们满足条件，则返回一个倍数间隔，否则返回一个跟踪间隔。这种解释导致类型:

makeInterval :: (Ord t) =>
  [I.Interval t] ->
  Either (DInterval TInterval t) (DInterval MInterval t)

现在我们有了类型，我们如何实现它？我们想重用我们的 makeMInterval 函数。

makeInterval is = maybe
                   (Left $ DInterval TInterval is)
                   Right
                   (makeMInterval is)

函数maybe接受三个参数:默认 b如果 Maybe 是 Nothing 时使用, 一个函数 a -> b如果 Maybe 是 Just a , 和 Maybe a .它返回默认值或将函数应用于 Maybe 值的结果。

我们的默认值是轨道间隔，因此我们为第一个参数创建一个左轨道间隔。如果可能是 Just (DInterval MInterval t) ，多重区间已经存在，所以只需将其粘贴到任一区间的右侧即可。最后，makeMInterval用于创建多个区间。