我正在努力使我的库的类型ghci显示尽可能直观,但在使用更高级的类型功能时遇到了很多困难.
假设我在一个文件中有这个代码:
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeOperators #-}
import GHC.TypeLits
data Container (xs::[*]) = Container
我在ghci中加载它,然后我输入以下命令:
ghci> :t undefined :: Container '[String,String,String,String,String]
不幸的是,ghci给了我相当难看的样子:
:: Container
((':)
*
String
((':)
* String ((':) * String ((':) * String ((':) * String ('[] *))))))
ghci已经删除了类型级字符串的糖.有没有办法阻止ghci做这个并给我一个漂亮的版本？
在相关的说明中,假设我创建了一个类型级别的Replicate函数
data Nat1 = Zero | Succ Nat1
type family Replicate (n::Nat1) x :: [*]
type instance Replicate Zero x = '[]
type instance Replicate (Succ n) x = …我想要一个TemplateHaskell函数variablesInScope :: Q [Name],它返回Name范围内所有变量的列表.TemplateHaskell显然有这些信息可用于实现像reify :: Name -> Q Info和的功能lookupValueName :: String -> Q (Maybe Name).
我想要的功能是否存在于某个地方,我只是忽略了它？或者它可以以某种方式轻松建立？
很明显,任何n元组都可以用一堆嵌套的2元组来表示.那么为什么它们在Haskell中不是一回事呢？这会破坏什么吗？
使这些类型等效将使得在元组上编写函数变得更加容易.例如,您可以只定义一个适用于所有元组的单个zip函数,而不是定义zip,zip2,zip3等.
当然,你可以使用嵌套的2元组,但它很丑陋并且没有规范的方法来执行嵌套(即我们应该嵌套到左边还是右边？).
假设我有一个非常大的数字(数百万/十亿+)这些简单的Foo数据结构:
data Foo = Foo
{ a :: {-# UNPACK #-}!Int
, b :: Int
}
随着这么多的浮动,有必要考虑他们消耗多少内存.
在64位机器上,每个Int都是8个字节,因此a只需要8个字节(因为它是严格的和解压缩的).但是会b占用多少内存？我想这会根据thunk是否被评估而改变,对吧？
我想在一般情况下这是不可能的,因为b可能依赖于任何数量的内存位置,只有在b需要评估的情况下才会留在内存中.但是,如果b只依赖(一些非常昂贵的操作)a呢？那么,是否有一种确定性的方式来判断将使用多少内存？
我在Haskell中进行懒惰评估的困难之一是难以推断内存使用情况.我认为复制thunk的能力会让我更容易.这是一个例子.
让我们创建一个非常大的列表:
let xs = [1..10000000]
现在,让我们创建一个不好的函数:
bad = do
print $ foldl1' (+) xs
print $ length xs
没有优化,这会占用几十MB的内存.垃圾收集器在折叠期间不能解除分配xs,因为稍后需要计算长度.
是否有可能重新实现此功能:
good = do
(xs1,xs2) <- copyThunk xs
print $ foldl1' (+) xs1
print $ length xs2
现在,xs1和xs2将表示相同的值,但在内存中也相互独立,因此垃圾收集器可以在折叠期间解除分配以防止内存浪费.(我认为这会稍微增加计算成本吗？)
显然在这个简单的例子中,重构代码可以很容易地解决这个问题,但似乎并不总是很明显如何重构.或者有时重构会大大降低代码清晰度.
我们可以使用扩展ConstraintKinds来扩展基类型类的功能以允许约束.例如,我们可以将未装箱的矢量作为仿函数:
class Functor f where
type FunctorConstraint f x :: Constraint
type FunctorConstraint f x = ()
fmap :: (FunctorConstraint f a, FunctorConstraint f b) => (a -> b) -> f a -> f b
instance Functor VU.Vector where
type FunctorConstraint VU.Vector x = VU.Unbox x
fmap = VU.map
我注意到自己在这种新风格中实现了相当大部分的基本库类型(基本上我希望能够在未装箱的向量和列表之间互换),并且我想知道是否已经存在我应该使用的库,或者如果我应该将我的肉体添加到hackage中.
编辑:此外,是否有计划将此直接添加到基地？它似乎不应该通过直接更新类定义来破坏其他任何东西.
Haskell有许多用于调试运行时性能问题的好工具,但是有哪些工具/经验法则可用于调试编译时性能问题？
具体来说,我的一些代码中的约束求解器将永远占用(从1-2秒到几分钟).我很确定这是由于我在约束中如何使用类型族,但我不知道在这种情况下哪种东西是昂贵的,或者如何看待约束求解器花费时间的位置.我最好的猜测是我对类型列表的操作之一是采用二次时间而不是线性时间.
让我们看一个为什么我怀疑约束求解器的例子.在我的文件中,我的代码如下:
class ExampleClass a where
type ExampleType a
f :: ExampleType a -> a
data ExampleData (xs :: [a]) = ...
instance
( Constraint1
, Constraint2
, ...
) => ExampleClass (ExampleData xs)
where
type ExampleType (ExampleData xs) = Int
f = undefined
当我将此文件加载到ghci中时
ghci> :l Example.hs
编译很快发生,远不到1秒.然后,我执行以下行:
ghci> let test = f Int :: ExampleData
没有实际的计算,但这仍然需要很长时间.ExampleData实例声明中的约束越多,所需的时间就越长.(实际上后来评估测试会立即发生.)我弄清楚如何调试这些性能问题的最好方法是逐个注释掉约束并查看哪些因素导致了性能损失.但这是非常耗时的,当这些限制涉及复杂类型的家庭时,它并不是真正的信息.
那么,我可以采用更好的方法来调试这个问题吗？
编辑:事实证明我发现了GHC中的一个错误.有一个与该bug相关联的脚本,表明约束求解器在输入上采用二次时间应该是线性的.
阅读这个问题和这篇博客文章让我更多地思考类型代数,特别是如何滥用它.
基本上,
1)我们可以将Either A B类型视为添加:A+B
2)我们可以将有序对(A,B)视为乘法:A*B
3)我们可以将函数A -> B视为取幂:B^A
这里有一个明显的模式:乘法是重复加法,并且取幂是重复乘法.这导致Knuth将向上箭头 ↑ 定义为取幂,↑↑定义为重复取幂,↑↑↑定义为重复↑↑,依此类推.因此,10↑↑↑↑10是一个巨大的数字.
我的问题是:如何在代数数据类型中表示函数↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑？看起来↑应该是一个具有无限数量的参数的函数,但这没有多大意义.会A?B简单地[A] -> B,因此A????B是[[[[A]]]]->B？
如果您可以解释Ackerman函数的外观或任何其他高增长函数,则可获得奖励积分.
类别理论和抽象代数处理函数可以与其他函数组合的方式.复杂性理论处理函数的计算难度.我很奇怪,我没有看到有人将这些研究领域结合起来,因为它们看起来像是如此自然的一对.有没有人这样做过？
作为一个激励性的例子,让我们来看看幺半群.众所周知,如果一个操作是一个幺半群,那么我们可以并行操作.
例如在Haskell中,我们可以简单地定义加法是整数的幺半群,如下所示:
instance Monoid Int where
mempty = 0
mappend = (+)
现在,如果我们想要计算0到999的总和,我们可以按顺序执行:
foldl1' (+) [0..999]
或者我们可以并行完成
mconcat [0..999] -- for simplicity of the code, I'm ignoring that this doesn't *actually* run in parallel
但是,并行化这个monoid只是因为mappend在恒定的时间内运行.如果不是这样怎么办？例如,列表是maoids不会运行不定时间(或空间!)的幺半群.我猜这就是Haskell中没有默认的并行mconcat函数的原因.最佳实现取决于幺半群的复杂性.
似乎应该有一种方便的方法来描述这两种幺半群之间的差异.然后,我们应该能够使用这些差异来注释我们的代码,并让程序根据monoid的复杂性自动选择要使用的最佳算法.