Simple Linux BASH script to swap two filenames

#!/bin/bash

if [ $# -lt 2 ]

then

echo "2 arguments needed."

exit

fi

mv $1 tmp

mv $2 $1

mv tmp $2

echo "Done!"

Haskell: Memoise arbitrary functions and monadic values

I recently got thinking about memoisation in Haskell functions to improve efficiency. Here are my notes -

Pure memoisation

This means adding memoisation to a function transparently (without changing the function signature).

i.e. write a function - memoise :: (a -> r) -> a -> r

so that all we have to do to memoise a function is - memoised_f = memoise f

This seems like an impossible thing to accomplish. Memoisation by definition requires a table/map in memory from argument to return values.

However by exploiting Lazy evaluation, and Compiler optimisations, we can accomplish this in haskell with relative ease. An example from the Haskell wiki -

-- The naive fibonacci function fib :: Int -> Integer fib 0 = 1 fib 1 = 1 fib n = fib (n-1) + fib (n-2)  -- Fast memoised fibonacci function memoised_fib :: Int -> Integer memoised_fib x = (map fib [0..]) !! x

Here we use lazy evaluation to build a map. And then exploit an optimisation of Haskell compilers that arguments to functions are only evaluated once. i.e. in this case that makes sure that (map fib [0..]) is only evaluated once.

It's perhaps clearer this way, which makes it clear that fibs is a constant that is only evaluated once -

-- Mapping from Indices to Fibonacci numbers fibs :: [Integer] fibs = map fib [0..]  -- Fast memoised fibonacci function memoised_fib :: Int -> Integer memoised_fib x = fibs !! x

Impure Memoisation

In general however, it is needed to add some kind of a stateful wrapper over the function to be memoised. IORefs in the IO Monad and State threading in the State Monad can be used for this. I however decided that it would be better to write a function to memoise any "Monadic Value" (m s). I also decided to use StateT Monad Transformer to store the State.

Here's a general solution that can memoise any monadic computation by wrapping it inside a StateT Monad Transformer -

module Main where  import qualified Data.Map as M(Map,empty,insert,lookup) import "monads-fd" Control.Monad.Trans(lift) import Control.Monad.Trans.State.Lazy(StateT(..))  -- Memoise arbitrary monadic computations by wrapping them inside a StateT Monad Transformer memoState :: (Ord k, Monad m) => (k -> m s) -> k -> StateT (M.Map k s) m s memoState f k = StateT $ \s ->         case M.lookup k s of             Nothing -> do                 z <- f k                 return (z, M.insert k z s)             Just z -> return (z, s)

Rather than explain how it works, here's an example of using it -

-- Our base monadic computation (IO) f :: Int -> IO String f x = do     putStr "Get Value #"     putStrLn $ show x     putStr "writesomething>"     s <- getLine     return s  -- Here's the IO monadic value (f) used in a memoised context -- First we wrap f inside StateT using memoState -- Then we chain it together using the usual monadic operations -- Note the use of Lift to perform actions in the IO monad fchain :: StateT (Stat Int String) IO String fchain = do     s <- f' 0     lift $ putStrLn s     s <- f' 1     lift $ putStrLn s     s <- f' 0     lift $ putStrLn s     s <- f' 1     lift $ putStrLn s     s <- f' 2     lift $ putStrLn s     return s         where f' = memoState f  -- The memoised computation fchain can now be run as a whole -- Thanks to memoisation, inspite of us invoking (f' 0) and (f' 1) twice, the user will be asked for their values only once. main :: IO () main = runStateT fchain $ M.empty

Works as advertised I'd say....