你如何在Haskell中创建一个通用的memoize函数？ [英] How do you make a generic memoize function in Haskell?

问题描述

我见过另一篇文章 ，但是在Haskell中有这样一个干净的方法吗？

作为第二部分，是否也可以在不使函数monadic的情况下完成？

解决方案

这主要遵循 http：/ /www.haskell.org/haskellwiki/Memoization 。

您需要一个类型为（a - > b）的函数。如果它不自己调用，那么
就可以写一个缓存返回值的简单包装器。存储此映射的
最佳方式取决于您可以利用
的哪些属性。订购是最低限度。使用整数
，您可以构造一个无限懒惰列表或树，其中包含值。

  type Cacher ab =（a  - > b） - > a  - > b 
 
 positive_list_cacher :: Cacher Int b 
 positive_list_cacher f n =（地图f [0 ..]）!! n 
  

或

  integer_list_cacher :: Cacher Int b 
 integer_list_cacher fn =（map f（interleave [0 ..] [-1，-2，..]）!! 
 index n其中
 index n | n <0 = 2 * abs（n） -  1 
 index n | n> = 0 = 2 * n 
   memoized版本，所以你改为传递它：
 
 
 
 b 
 $ b 
  f_with_memo ::（a  - > b） - > a  - > b 
 f_with_memo memoed base = base_answer 
 f_with_memo memoed arg = calc（memoed（simpler arg））
  
当然，memoized版本是我们正在尝试定义。
 
 
 
但是我们可以从创建缓存输入的函数开始： 
 
 
我们可以通过传入一个创建缓存值的
结构的函数来构造一个级别。除了我们需要创建已有的f 
版本外，缓存的函数传入。
 
 
 
感谢懒惰，这是没有问题的： 
 
 
  memoize cacher f = cached其中
 cached = cacher（f cached）
  
那么我们需要的就是使用它：
  exposed_f = memoize cacher_for_f f 
  
这篇文章给出了如何在函数的
输入中选择一个类型类来完成上述操作的提示，而不是选择显式
缓存功能。这可以非常好 - 而不是显式地为每个输入类型的组合构造一个缓存
将类型a和b的缓存结合到一个缓存中，以获取a和b的函数。 / p> 
 
 
最后一个警告：使用这种懒惰的技术意味着缓存永远不会缩小，
只会增长。如果你改用IO monad，你可以管理这个，但
明智地做这个取决于使用模式。
 
I've seen the other post about this, but is there a clean way of doing this in Haskell?

As a 2nd part, can it also be done without making the function monadic?
解决方案
This largely follows http://www.haskell.org/haskellwiki/Memoization.

You want a function of type (a -> b).  If it doesn't call itself, then
you can just write a simple wrapper that caches the return values.  The 
best way to store this mapping depends on what properties of a you can
exploit.  Ordering is pretty much a minimum.  With integers 
you can construct an infinite lazy list or tree holding the values.
type Cacher a b = (a -> b) -> a -> b

positive_list_cacher :: Cacher Int b
positive_list_cacher f n = (map f [0..]) !! n
or
integer_list_cacher :: Cacher Int b
integer_list_cacher f n = (map f (interleave [0..] [-1, -2, ..]) !!
    index n where
        index n | n < 0  = 2*abs(n) - 1
        index n | n >= 0 = 2 * n
So, suppose it is recursive.  Then you need it to call not itself, but
the memoized version, so you pass that in instead:
f_with_memo :: (a -> b) -> a -> b
f_with_memo memoed base = base_answer
f_with_memo memoed arg  = calc (memoed (simpler arg))
The memoized version is, of course, what we're trying to define.

But we can start by creating a function that caches its inputs:

We could construct one level by passing in a function that creates a 
structure that caches values.  Except we need to create the version of f
that already has the cached function passed in.

Thanks to laziness, this is no problem:
memoize cacher f = cached where
         cached = cacher (f cached)
then all we need is to use it: 
exposed_f = memoize cacher_for_f f
The article gives hints as to how to use a type class selecting on the 
input to the function to do the above, rather than choosing an explicit 
caching function.  This can be really nice -- rather than explicitly 
constructing a cache for each combination of input types, we can implicitly
combine caches for types a and b into a cache for a function taking a and b.

One final caveat: using this lazy technique means the cache never shrinks,
it only grows.  If you instead use the IO monad, you can manage this, but
doing it wisely depends on usage patterns.

                        
这篇关于你如何在Haskell中创建一个通用的memoize函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！