有没有一种自动方式来记忆Haskell中的全局多态值？ [英] Is there an automatic way to memoise global polymorphic values in Haskell?

问题描述

多态常量，如 5 :: Num a =>一个，并不是真正的常量，而是一个字典参数的函数。因此，如果您定义

  primes :: Num n => [n] 
 primes = ... 
  

^{当然不好的例子有没有什么理由让它具有多态性......我真正感兴趣的是如果你试图在全球范围内记忆一个非平凡的多态函数，例如 memo-trie s。}

，那么这个序列将不会在来自不同网站的呼叫之间共享，这并不好的表现。 （难道这不是Haskell标准为可怕的单态限制保护我们的主要原因吗？）

我可以看到如何强制共享的唯一方式是拥有一个单形态为每个约束类的实例坐下来的标签。例如：

  erastothenes :: Num n =>> [n] 
 erastothenes = ... 
 
 class（Num n）=> HasPrimes n其中
  -  | @'primes'≡'erastothenes'@ 
 primes :: [n] 
 
 integerPrimes :: [Integer] 
 integerPrimes = erastothenes 
 
实例HasPrimes整数，其中
 primes = integerPrimes 
  

...这对于优雅。

有没有更好的方法来实现这样的memoisation？

解决方案

<如果您启用 ConstraintKinds 和 ExistentialQuantification （或 GADT ）你可以使用类型类字典：

$ p $ { - ＃LANGUAGE Con​​straintKinds，ExistentialQuantification＃ - }

数据字典a = a => Dict


如果我们尝试了这一点

  fibs :: Num n => [b] 
 fibs = 1：1：zipWith（+）fibs（drop 1 fibs）
 
 fibs':: [Integer] 
 fibs'= fibs 
 
 
 fibsWithDict :: Dict（Num n） - > [n] 
 fibsWithDict Dict = fs 
其中
 fs = 1：1：zipWith（+）fs（drop 1 fs）
 
 fibs''[整数] 
 fibs''= fibsWithDict字典
  

在GHCi中我们看到

 λ> ：set + s 
λ> 
λ> fibs！ 29 
 832040 
（2.66秒，721235304字节）
λ> 
λ> fibs！ 29 
 832040 
（2.52秒，714054736字节）
λ> 
λ> 
λ> fibs'！ 29 
 832040 
（2.67秒，713510568字节）
λ> 
λ> fibs'！ 29 
 832040 
（0.00秒，1034296字节）
λ> 
λ> 
λ> fibs''!! 29 
 832040 
（0.00秒，1032624字节）
  

所以 fibs''是三个立即记忆的唯一实现。

请注意，我们必须在 Dict 构造函数。否则，我们将得到一个关于 n 的错误，而不是被限制为有一个 Num 实例（就像你期望的那样签名只是 fibsWithDict :: a - > [n] ）。

这是一个完整的解决方案，可以考虑将> fibsWithDict Dict 作为一个表达式，它可以立即在任何类型的对象上进行记忆（只要它是 Num ）。例如：



 λ> （fibsWithDict Dict !! 29）:: Double 
 832040.0 
（0.00秒，1028384字节）
  

编辑：它看起来像这个显式字典传递在这里是不必要的，可以隐式地通过使用 ScopedTypeVariables 与本地绑定来完成：

  { - ＃LANGUAGE ScopedTypeVariables＃ - } 
 
 fibsImplicitDict :: forall a。 Num a => [$] 
 fibsImplicitDict 
 = let fs :: [a] 
 fs = 1：1：zipWith（+）fs（drop 1 fs）
 in 
 fs 
  

（感谢bennofs的洞察力！）

Polymorphic "constants", like 5 :: Num a => a, aren't really constants but functions of a dictionary argument. Hence, if you define

primes :: Num n => [n]
primes = ...

^{Bad example of course, there's no good reason here to have it polymorphic... what I'm really interested is if you try to globally memoise a nontrivial polymorphic function, with e.g. memo-tries.}
then this sequence won't be shared between calls from different sites, which isn't nice in terms of performance. (Isn't this the main reason the Haskell standard blessed us with the Dreaded Monomorphism Restriction?)

The only way I can see how to enforce sharing is to have a monomorphic "tag" sitting around for every instance of the constraining class. E.g.

erastothenes :: Num n => [n]
erastothenes = ...

class (Num n) => HasPrimes n where
  -- | @'primes' ≡ 'erastothenes'@
  primes :: [n]

integerPrimes :: [Integer]
integerPrimes = erastothenes

instance HasPrimes Integer where
  primes = integerPrimes

... which isn't nice in terms of elegance.

Is there any nicer way to implement such a memoisation?

解决方案

If you enable ConstraintKinds and ExistentialQuantification (or GADTs) you can reify type class dictionaries:

{-# LANGUAGE ConstraintKinds, ExistentialQuantification #-}

data Dict a = a => Dict

If we try this out

fibs :: Num n => [n]
fibs = 1 : 1 : zipWith (+) fibs (drop 1 fibs)

fibs' :: [Integer]
fibs' = fibs


fibsWithDict :: Dict (Num n) -> [n]
fibsWithDict Dict = fs
  where
    fs = 1 : 1 : zipWith (+) fs (drop 1 fs)

fibs'' :: [Integer]
fibs'' = fibsWithDict Dict

in GHCi we see

λ> :set +s
λ> 
λ> fibs !! 29
832040
(2.66 secs, 721235304 bytes)
λ> 
λ> fibs !! 29
832040
(2.52 secs, 714054736 bytes)
λ> 
λ> 
λ> fibs' !! 29
832040
(2.67 secs, 713510568 bytes)
λ> 
λ> fibs' !! 29
832040
(0.00 secs, 1034296 bytes)
λ> 
λ> 
λ> fibs'' !! 29
832040
(0.00 secs, 1032624 bytes)

So fibs'' is the only implementation of the three that immediately memoizes.

Note that we have to pattern match on the Dict constructor. Otherwise, we will get an error about n not being constrained to have a Num instance (like you would expect if our signature was just fibsWithDict :: a -> [n]).

This is a full solution since you can consider fibsWithDict Dict to be an expression that memoizes immediately at any type you throw at it (as long as it's an instance of Num). For example:

λ> (fibsWithDict Dict !! 29) :: Double
832040.0
(0.00 secs, 1028384 bytes)

EDIT: It looks like this explicit dictionary passing isn't necessary here and can be done implicitly by using ScopedTypeVariables with a local binding:

{-# LANGUAGE ScopedTypeVariables #-}

fibsImplicitDict :: forall a. Num a => [a]
fibsImplicitDict
  = let fs :: [a]
        fs = 1 : 1 : zipWith (+) fs (drop 1 fs)
    in
    fs

(Thanks to bennofs for the insight here!)

这篇关于有没有一种自动方式来记忆Haskell中的全局多态值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！