是否有可能在haskell中有一套理解？

Question

在Haskell中,我们有列表生成器,例如:

[x+y | x<-[1,2,3], y<-[1,2,3]]

我们得到了

[2,3,4,3,4,5,4,5,6]

是否有可能有一个集合生成器,如果它已经在列表中,它不会自动添加元素？

在我们的示例中,我们将获得:

[2,3,4,5,6]

如果是这样,怎么样？如果它尚未实现,您将如何实现它？

Answer 1

Haskell可以做到这一点,但不是完全开箱即用的.

基本的基础是列表理解也可以写成monadic中的monadic绑定链:

Prelude> [x+y | x<-[1,2,3], y<-[1,2,3]]
[2,3,4,3,4,5,4,5,6]
Prelude> [1,2,3] >>= \x -> [1,2,3] >>= \y -> return (x+y)
[2,3,4,3,4,5,4,5,6]

...或者,具有更好的可读性do-syntax(这是一元结合的语法糖)

Prelude> do x<-[1,2,3]; y<-[1,2,3]; return (x+y)
[2,3,4,3,4,5,4,5,6]

事实上,有一种语言扩展也将所有列表理解转化为这种monadic链的语法糖.元组(又名作家)monad中的示例:

Prelude> :set -XMonadComprehensions 
Prelude> [x+y | x <- ("Hello", 4), y <- ("World", 5)] :: (String, Int)
("HelloWorld",9)

所以,我们所需要的只是一套monad.这是明智的足够了,但是Data.Set.Set是不是在单子Hask(所有的Haskell类型类别),但只有唯一的子类别满足Ord约束(这是需要查找/以避免重复).在集合的情况下,有一个hack允许从实际的monad实例隐藏该约束; 它用在set-monad包装中.Etvoilà:

Prelude Data.Set.Monad> [x+y | x<-fromList[1,2,3], y<-fromList[1,2,3]]
fromList [2,3,4,5,6]

需要的黑客是instance Monad Set有代价的.它的工作原理如下:

{-# LANGUAGE GADTs, RankNTypes #-}
import qualified Data.Set as DS

data Set r where
  Prim :: (Ord r => DS.Set r) -> Set r
  Return :: a -> Set a
  Bind   :: Set a -> (a -> Set b) -> Set b
  ...

这意味着:类型的值Data.Set.Monad.Set Int实际上并不包含一组具体的整数.相反,它包含一个计算的抽象语法表达式,该表达式生成一个集合作为结果.这对于性能来说并不是很好,特别是它意味着不会共享值.所以不要将它用于大集.

有一个更好的选择:直接使用它作为正确类别中的monad (它只包含可开始的可订​​购类型).不幸的是,这需要更多语言弯曲,但这是可能的; 我在constrained-categories图书馆里做了一个例子.

Answer 2

如果您的价值可以放入Data.Set.Set(即他们在课堂上Ord),您只需申请Data.Set.toList . Data.Set.fromList到您的清单:

Prelude> import Data.Set
Prelude Data.Set> Data.Set.toList . Data.Set.fromList $ [x+y | x<-[1,2,3], y<-[1,2,3]]
[2,3,4,5,6]

这种复杂性将是O(n log n).

如果类型服从(Eq a, Hashable a),您可以Data.HashSet以相同的方式使用.平均复杂性是O(n).

如果你拥有的只是Eq,你必须得到类似的东西Data.List.nub:

Prelude> import Data.List
Prelude Data.List> nub [x+y | x<-[1,2,3], y<-[1,2,3]]
[2,3,4,5,6]

但复杂性本质上是二次的.