runmemo (empty) → 1.0.0.0

raw patch · 5 files changed

+221/−0 lines, 5 filesdep +basedep +data-memocombinatorsdep +timesetup-changed

Dependencies added: base, data-memocombinators, time

Files

• LICENSE +30/−0
• Setup.hs +2/−0
• runmemo.cabal +93/−0
• src/Data/RunMemo.hs +67/−0
• test/test-race.hs +29/−0

@@ -0,0 +1,30 @@+Copyright (c) 2012, Dan Burton++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Dan Burton nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,93 @@+name:                runmemo+version:             1.0.0.0+synopsis:            A simple memoization helper library++description:+  This library encourages you to do memoization+  in three separate steps:+  .+  (1) Create a memoizable function+  .+  (2) Create or select an appropriate memoizer+  .+  (3) Run the memoizer on the memoizable function+  .+  Let's start with the first.+  When you create a memoizable function,+  you should use the @self@ convention,+  which is that the first input to the function is @self@,+  and all recursive calls are replaced with @self@.+  One common convention that goes well with the @self@ convention+  is using a helper function @go@, like so:+  .+  @+  fib :: Memoizable (Integer -> Integer)+  fib self = go+  \  where go 0 = 1+  \        go 1 = 1+  \        go n = self (n-1) + self (n-2)+  @+  .+  Now for the second. For this example,+  we need a Memoizer that can handle an @Integer@ input,+  and an @Integer@ output. @Data.MemoCombinators@ provides+  @integral@, which handles any @Integral@ input, and+  any output. @Data.MemoUgly@ provides @memo@,+  which can memoize any function @a -> b@, given an @Ord@ instance+  for @a@.+  .+  Third, let's run our memoizers!+  Since we have decoupled the definition of the memoized function+  from its actual memoization, we can create multiple+  memoized versions of the same function if we so desire.+  .+  @+  import qualified Data.MemoUgly as Ugly+  import qualified Data.MemoCombinators as MC+  .+  fibUgly :: Integer -> Integer+  fibUgly = runMemo Ugly.memo fib+  .+  fibMC :: Integer -> Integer+  fibMC = runMemo MC.integral fib+  @+  .+  You could easily do the same with @Data.MemoTrie.memo@,+  @Data.Function.Memoize.memoize@, etc.+  .+  Using this technique, you can create local memoized functions+  whose memo tables are garbage collected as soon as+  they are no longer needed.+++homepage:            https://github.com/DanBurton/runmemo+license:             BSD3+license-file:        LICENSE+author:              Dan Burton+maintainer:          danburton.email@gmail.com+copyright:           (c) Dan Burton 2012++category:            Data+build-type:          Simple+cabal-version:       >=1.8++library+  hs-source-dirs:    src+  exposed-modules:   Data.RunMemo+  extensions:        NoImplicitPrelude+  ghc-options:       -Wall++test-suite test-race+  type:            exitcode-stdio-1.0+  hs-source-dirs:  test, src+  main-is:         test-race.hs+  build-depends:   data-memocombinators == 0.4.*, base == 4.*, time == 1.4.*++source-repository head+  type:     git+  location: git@github.com:DanBurton/runmemo.git++source-repository this+  type:     git+  location: git@github.com:DanBurton/runmemo.git+  tag:      runmemo-1.0.0.0

@@ -0,0 +1,67 @@+-- | Run 'Memoizer's on 'Memoizable' functions.+-- The beauty of 'runMemo' is that it decouples+-- the definition of a Memoizable function+-- from the process of actually memoizing it.+module Data.RunMemo (+    Memoizable+  , Memoizer+  , runMemo+  , noMemo+  ) where+++-- | A memoizable thing takes itself as input+-- and produces itself.+-- +-- Usually you will use this for functions:+-- e.g. @foo :: Memoizable (String -> String)@,+-- which desugars to @foo :: (String -> String) -> String -> String@+type Memoizable a = a -> a+++-- | A memoizer from a to b+-- takes a function with input a and output b+-- and memoizes it+-- +-- If you have a @Memo Foo@ from @Data.MemoCombinators@,+-- then it is also a @Memoizer Foo b@, which can unify+-- with any type @b@.+type Memoizer a b = (a -> b) -> a -> b+++-- | Given a memoizable function and a memoizer,+-- put two and two together!+-- +-- Your memoizable should look something like this:+-- +-- > foo :: Memoizable (Foo -> Bar)+-- > foo self = go+-- >   where go x = ... self a ...+-- +-- The main feature is that @self@ is the first input+-- of a @Memoizable@ function,+-- @self@ and is used for all recursive calls.+-- +-- Memoizables can take as many arguments as you like,+-- given an appropriate Memoizer+-- +-- > foo2 :: Memoizable (Bar -> Baz -> Quux)+-- > foo2 self = go+-- >   where go x y = ... self a b ...+-- +-- Using @Data.MemoCombinators@, for example,+-- you could do @runMemo (Memo.memo2 Memo.bar Memo.baz) foo2@+runMemo :: Memoizer a b -> Memoizable (a -> b) -> a -> b+runMemo memo f = fix (f . memo)+  where fix h = let x = h x in x+        (g . h) x = g (h x)+++-- | The trivial memoizer.+-- It doesn't actually memoize anything,+-- it just passes values straight through+-- to the original function.+-- +-- It is not recommended that you actually use this memoizer.+noMemo :: Memoizer a b+noMemo f = f

@@ -0,0 +1,29 @@+module Main where++import Data.MemoCombinators as Memo+import Data.RunMemo+import System.Exit+import Data.Time.Clock++fib :: Memoizable (Integer -> Integer)+fib self = go+  where go 0 = 1+        go 1 = 1+        go n = self (n-1) + self (n-2)++time :: IO () -> IO NominalDiffTime+time a = do+  start <- getCurrentTime+  a+  stop <- getCurrentTime+  return $ diffUTCTime stop start++main :: IO ()+main = do+  putStrLn "Evaluating with Memo.integral"+  mtime <- time $ runMemo Memo.integral fib 30 `seq` putStrLn "Evaluated"+  putStrLn "Evaluating with noMemo"+  ntime <- time $ runMemo noMemo fib 30 `seq` putStrLn "Evaluated"+  if mtime < ntime+    then exitSuccess+    else exitFailure