Памятка для последующих фолдов - PullRequest
Новая
       42

Памятка для последующих фолдов

0 голосов
/ 29 июня 2018

Я ищу технику, которая позволяет запоминать между последующими вызовами свертки списки, которые находятся перед добавлением.

Я посмотрел на memoize library , но, похоже, это не поддерживает запоминание функций более высокого порядка, как в случае сгибов.

Я также попробовал технику с ленивой оцененной картой результатов, но безрезультатно.

Вот простой пример кода: 

module Main where

import Data.Time

printAndMeasureTime :: Show a => a -> IO ()
printAndMeasureTime a = do
  startTime <- getCurrentTime
  print a
  stopTime <- getCurrentTime
  putStrLn $ " in " ++ show (diffUTCTime stopTime startTime)

main = do
  let as = replicate 10000000 1
  printAndMeasureTime $ foldr (-) 0 as -- just to resolve thunks
  printAndMeasureTime $ sum as
  printAndMeasureTime $ sum (1:as) -- recomputed from scratch, could it reuse previous computation result?
  printAndMeasureTime $ length (as)
  printAndMeasureTime $ length (1:as) -- recomputed from scratch, could it reuse previous computation result?

и вывод: 

0
 in 1.125098223s
10000000
 in 0.096558168s
10000001
 in 0.104047058s
10000000
 in 0.037727126s
10000001
 in 0.041266456s

Время подсказывает, что складки вычисляются с нуля. Есть ли способ заставить последующие сгибы повторно использовать результаты предыдущих сгибов?

1 Ответ

0 голосов
/ 01 июля 2018

Создайте тип данных! 

module List (List, _elements, _sum, _length, toList, cons) where

data List = List
  { _elements :: [Int]
  , _sum :: !Int
  , _length :: !Int
  }

toList :: [Int] -> List
toList xs = List xs (sum xs) (length xs)

cons :: Int -> List -> List
cons x (List xs t n) = List (x:xs) (x+t) (1+n)

Обратите внимание, что тип List экспортируется, а конструктор List - нет, поэтому единственный способ создать List - использовать функцию toList (обычно называемую «умным конструктором»).

...