7

有没有办法强制 GHC 在特定值的生命周期内对特定计算进行重击？

我显然可以将值放入记录中，为所述计算的结果创建惰性记录条目，并创建一个生成器函数来构建记录并将值复制到所述条目中。

我讨厌每次我想要它时都需要从记录中提取原始值。而且 Haskell 没有像 C++ 或 Java 这样的临时多态 is-a 关系。

是否有任何技巧可以在具有相同参数的函数的多个不相关调用中记忆值？

我可以模糊地想象各种依赖类型形式的技巧，这些技巧可以有效地告诉编译器多种用法即将到来。Haskell 中没有任何依赖类型，但可能是隐式参数？我想不是，但我想我会问。也许是一个编译器？

想象一下，我有一个Necklace数据结构向量，我需要一个有理数的结果向量，存储为一个公分母和一个分子向量。

{-# LANGUAGE ImplicitParams #-}
import qualified Data.Vector as V

data Necklace = Necklace { ... }
necklace_length n = ...

denominator :: (necklaces :: V.Vector Necklace) => Int
denominator = V.foldl' lcm 30 $ V.map necklace_length ?necklaces

numerators :: (necklaces :: V.Vector Necklace) => V.Vector Int
numerators = V.map f ?necklaces
  where f x = ... denominator ...

kittytoy :: (necklaces :: V.Vector Necklace) => Meow -> ...
kittytoy = \meow -> ... numerators ...

先验地，我希望，如果我调用kittytoy几百万次，每次都使用不同的参数meow，那么 GHC 会生成调用numerators一百万次的代码，每次都使用相同的隐式参数necklaces。

尽管如此，很明显numerators只需要调用一次，第一次?necklaces被分配，这意味着 GHC 可能会注意到这种优化。

甚至应该有一种显式的代码重构方法，使用模板 haskell 通过生成类似代码?numerators = numerators并添加numerators :: V.Vector Int到调用它的函数的类型约束来显式传递 thunk。

4

2 回答 2

7

您可能正在寻找由data-memocombinators实现的纯记忆。基本上，它的工作原理是创建一个（惰性的，可能是无限的）树结构，其中包含每个叶子上函数的所有可能值，然后创建一个简单地访问相关位置的值的新函数。例如，你可以为这样的函数编写一个 memoiser Bool -> a：

memoBool :: (Bool -> a) -> (Bool -> a)
memoBool f =
    let fTrue = f True
        fFalse = f False
    in \b -> if b then fTrue else fFalse

在这种情况下，“树结构”相当盆景，只有两片叶子。

data-memocombinators 将其封装在Memo a类型中，定义为forall r. (a -> r) -> (a -> r)，并带有有用的组合器，例如pair :: Memo a -> Memo b -> Memo (a, b)（阅读：如果你可以记忆参数类型的函数a，和参数类型的记忆函数b，你可以记忆参数类型的函数(a, b)）。

这是纯粹的，非常优雅的，依赖于基本上所有 Haskell 实现所实现的共享（这与使您的记录想法起作用的东西相同）。不幸的是，它也不是很快，所以在实际使用中，您可能希望使用丑陋Map的备忘录，它在幕后使用可变的（但公开了一个外部纯接口）。

于 2012-04-06T21:34:53.840 回答
0

正如Philip JF在此处的回答type中所指出的，现在定义了类型约束的同义词这一事实产生了另一种似是而非的方法。

您可能会为为所有各种派生值创建隐式参数的类型约束创建同义词：

type Necklaces = (necklaces :: V.Vector Necklace,
                  denominator :: Int,
                  numerators :: V.Vector Int)

kittytoy :: (Necklaces) => Meow -> ...

您最初会分配所有值，例如?numerators使用某种形式的模板 Haskell 构造。我会玩它，看看它是否有效。

于 2012-04-07T12:54:24.623 回答