logo标签列表

Haskell新手关于类型的问题

haskell
9

我完全不了解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-intervals）感兴趣，这些对象由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

当is是MInterval或TInterval时，调用order函数形式为order (MIntervalStuff is)或order (TIntervalStuff is)。这看起来不太好。我也不想复制函数（我有很多与多个和轨道间隔有关的函数，以及一些其他的d间隔定义，如等长多个和轨道间隔）。

我感到完全错误，并且错过了Haskell中类型的一些重要点（和/或无法在此处忘记足够的OO编程）。因此，作为一个新手问题，什么是在Haskell中处理这种情况的最佳方法？我必须忘记引入MInterval和TInterval并只使用一种类型吗？

非常感谢您的帮助，

Garulfo

3
顺便提一下，foldr (&&) True 的结果等同于 and。 - Nefrubyr
4个回答
5

编辑：这个方法与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比调用错误更符合惯例。

关于Maybe的更多解释：

让我们来看看您的函数makeInterval。这个函数应该接受一个Interval列表，如果它们满足条件，则返回多个区间，否则返回跟踪区间。这个解释导致了以下类型：

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值的结果。
我们的默认值是跟踪间隔，因此我们为第一个参数创建了一个Left跟踪间隔。如果Maybe是Just (DInterval MInterval t)，则多重间隔已经存在，所需的只是将其插入到either的右侧。最后，makeMInterval用于创建多重间隔。
非常感谢你们所有人。这正是我正在寻找的。此外，我认为我将能够使用相同的方法来考虑我的额外属性（所有间隔长度相同，单位长度，...），例如数据DInterval a b t = DInterval [I.Interval t]，其中a将作为MInterval或TInterval，b作为Balanced，Unit等。 - garulfo
关于Maybe的笔记...我唯一真正理解的是Maybe是一个重要的概念。我的意思是，我理解Maybe局部（用来表示可能失败的计算），但是不太理解如何在Maybe中使用>>=（在某些教程中我发现这很不错）。然而，将其用于日常仍然不清楚。如果我想要同时定义makeInterval和makeMInterval，那么我会遇到麻烦，因为在makeMInterval中，我期望的是[I.Interval t]，而不是[Maybe(I.Interval t)]。好吧，我需要多读一些相关资料。 - garulfo
你读过LYAH的Maybe章节了吗？http://learnyouahaskell.com/a-fistful-of-monads#getting-our-feet-wet-with-maybe - John L
3
你需要的是一个类型类。类型类是Haskell中实现重载的方式。类型类是许多类型共享的通用结构。在你的情况下，你想创建一个包含所有具有order函数的类型的类：
 class Dimensional a where
     order :: a -> Int

这段话的意思是有一类名为Dimensional的类型a，对于属于这个类的每种类型，都有一个名为order的函数a -> Int。现在您需要将所有类型声明为属于该类：
 instance Dimensional MInterval where
     order (MInterval is) = length is

等等。您还可以声明针对来自给定类的事物的函数，如下所示：

 isOneDimensional :: (Dimensional a) => a -> Bool
 isOneDimensional interval = (order interval == 1)

类型声明可以解读为“对于所有属于类型类Dimensional的类型a，此函数接受a并返回一个Bool值”。
我认为类可以看作是数学中的代数结构（虽然并非完全相同，因为您不能强制执行某些逻辑限制，但…）：您声明了一个类型属于某个类的要求（在类比中，必须定义操作以便其属于某个代数结构），然后针对每个特定类型，您说明所需函数的具体实现（在类比中，每个特定集合的具体函数是什么）。
例如，以群为例。群必须具有标识、每个元素的逆和乘法：
 class Group a where:
        identity :: a
        inverse  :: a -> a 
        (<*>)      :: a -> a -> a

整数在加法下形成一个群：

instance Group Integer where:
        identity  = 0
        inverse x = (- x)
        x <*> y     = x + y

请注意，这并不能解决重复的问题，因为您需要实例化每种类型。
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接