Haskell中是否存在任何隐式记忆？

Question

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

我显然可以将值放入记录中,为所述计算的结果创建惰性记录条目,并创建一个构建记录的制造商函数,并将值置于所述条目中.

我讨厌每次我想要它时都需要从记录中取出原始值.并且Haskell没有任何特殊的多态性 - 像C++或Java这样的关系.

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

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

---

想象一下,我有一个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通过生成代码来显式传递thunk,?numerators = numerators并添加numerators :: V.Vector Int调用它的函数的类型约束.

Answer 1

您可能正在寻找纯数据,因为数据记忆合作者已经实现了这一点.基本上,它的工作原理是创建一个(懒惰的,可能是无限的)树结构,其中包含每个叶子上函数的所有可能值,然后创建一个简单访问相关位置值的新函数.例如,您可以为这样的函数编写备忘录Bool -> a:

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

在这种情况下,"树结构"是盆景,只有两片叶子.

数据包memocombinators这个向上的Memo a类型,其定义为forall r. (a -> r) -> (a -> r),与等是有用的组合子pair :: Memo a -> Memo b -> Memo (a, b)(读:如果你可以memoise参数类型的功能a,和参数类型的memoise功能b,可以memoise参数类型的函数(a, b)).

这是纯粹的,非常优雅,依赖于基本上所有Haskell实现实现的共享(这与使您的记录构思工作相同).不幸的是,它也不是很快,所以在实际应用中你可能想要使用uglymemo,它Map在幕后使用了一个可变的(但是暴露了一个外部纯接口).