haskell - 内存类型为 [Integer] -> a 的函数

Question

我的问题是如何有效地记住一个昂贵的函数 f :: [Integer] -> a为所有有限整数列表定义并具有属性 f . sort = f ?

我的典型用例是给定一个列表 as整数我需要获得值 f (a:as)对于各种整数 a，所以我想同时建立一个有向标记图，其顶点是整数列表及其函数值的对。由 a from (as, f as) to (bs, f bs) 标记的边存在当且仅当 a:as = bs。

从 brilliant answer by Edward Kmett 窃取我简单地复制了

{-# LANGUAGE BangPatterns #-}
data Tree a = Tree (Tree a) a (Tree a)
instance Functor Tree where
  fmap f (Tree l m r) = Tree (fmap f l) (f m) (fmap f r)

index :: Tree a -> Integer -> a
index (Tree _ m _) 0 = m
index (Tree l _ r) n = case (n - 1) `divMod` 2 of
  (q,0) -> index l q
  (q,1) -> index r q

nats :: Tree Integer
nats = go 0 1
  where go !n !s = Tree (go l s') n (go r s')
          where l = n + s
                r = l + s
                s' = s * 2

并根据我的问题调整了他的想法

-- directed graph labelled by Integers
data Graph a = Graph a (Tree (Graph a))
instance Functor Graph where
  fmap f (Graph a t) = Graph (f a) (fmap (fmap f) t)

-- walk the graph following the given labels
walk :: Graph a -> [Integer] -> a
walk (Graph a _) [] = a
walk (Graph _ t) (x:xs) = walk (index t x) xs

-- graph of all finite integer sequences
intSeq :: Graph [Integer]
intSeq = Graph [] (fmap (\n -> fmap (n:) intSeq) nats)

-- could be replaced by Data.Strict.Pair
data StrictPair a b = StrictPair !a !b
  deriving Show

-- f = sum modified according to Edward's idea (the real function is more complicated)
g :: ([Integer] -> StrictPair Integer [Integer]) -> [Integer] -> StrictPair Integer [Integer]
g mf [] = StrictPair 0 []
g mf (a:as) = StrictPair (a+x) (a:as)
  where StrictPair x y = mf as

g_graph :: Graph (StrictPair Integer [Integer])
g_graph = fmap (g g_m) intSeq

g_m :: [Integer] -> StrictPair Integer [Integer]
g_m = walk g_graph

这工作正常，但作为函数 f与出现的整数的顺序无关(但不依赖于它们的计数)，对于所有等于 ordering 的整数列表，图中应该只有一个顶点。

我如何实现这一目标？

Answer 1

定义g_m' = g_m . sort怎么样？ ，即您只需先对输入列表进行排序，然后再调用您的内存功能？

我有一种感觉，这是你能做的最好的事情，因为如果你想让你的内存图只包含排序的路径，那么在构建路径之前，有人将不得不查看列表的所有元素。

根据您的输入列表的外观，以减少树分支的方式转换它们可能会有所帮助。例如，您可以尝试排序和取差异:

original input list:   [8,3,14,8,5]
sorted:                [3,3,8,8,14]
diffed:                [3,0,5,0,6] -- use this as the key

变换是双射，树的分支较少，因为涉及的数字较少。