Related to: http://stackoverflow.com/questions/16128645/ Haskell source file I implemented the algorithm which is written in the question.

NatSet.hs

-- Related to: http://stackoverflow.com/questions/16128645/
-- Haskell source file I implemented the algorithm which is written in the question.
-- this program is written under GHC 7.4.2 @ Ubuntu 12.10,
-- requires mtl (Monad transformers) module.
-- To test this:
--  * place this file on a directory
--  * run GHCi there
--  * load NatSet module (:load NatSet)
--  * give some list of Int to printClosure function.
--    example: > printClosure [7, 20, 17, 100] 
-- 
-- This version differs from the pseudocode on some point.
-- Difference are:
--  * To implement variable-update semantics, it uses Control.Monad.State monad. (Can it affect the performance?)
--  * Some set are implemented using List as container, some are IntSet, IntMap.
--  * Does not use recoverEquation. Instead, it remembers how a number is decomposed to the expression of two numbers.
--    the equivalence of the function in the pseudocode
--         requiredNumbers :: Int -> Set of (Set of Int)
--    is
--         required :: Int -> List of (IntSet, Description)
--    where Description stores the expression which caclulates n using the numbers in its pair IntSet.
-- 

module NatSet where

import Control.Applicative
import Control.Monad
import Control.Monad.State

import Data.List (find)
import Data.IntSet (IntSet, deleteFindMin, (\\))
import qualified Data.IntSet as ISet
import Data.IntMap (IntMap)
import qualified Data.IntMap as IMap

import Debug.Trace

type Description = String

data Method = Method {
                req :: Int -> [[Int]],
                desc :: [Int] -> Description } 

infixr 5 +++
(+++) = ISet.union

required :: Int -> [(IntSet, Description)]
required n = if (n > 1) then
                concat $ byMethod <$> [pow, mult, add] <*> pure n
             else
                [(ISet.empty, "(exists)")]
byMethod method = map (\l -> (ISet.fromList l, desc method l)) . req method

add = Method add_list add_descr
  where
  add_list n = map (\k -> [k, n-k]) [1..((n+1)`div`2)]
  add_descr (j:k:[]) = (show j) ++ " + " ++ (show k)
mult = Method mult_list mult_descr
  where
  mult_list n = map (\k -> [k, n `div` k]) $
                filter (\k -> (n `mod` k) == 0) $
                takeWhile (\k -> k*k <= n) [2..]
  mult_descr (j:k:[]) = (show j) ++ " * " ++ (show k)
pow = Method pow_list pow_descr
  where
  pow_list n = concatMap (\j -> log_int j n) $
               takeWhile (\j -> j*j <= n) [2..]
    where
    log_int j n = let k = truncate (logBase (fromIntegral j) (fromIntegral n))
                  in if j^k == n then [[j, k]] else []
  pow_descr (j:k:[]) = (show j) ++ " ^ " ++ (show k)

type SearchMinMap a = State (IntMap a, Int)
updateMin newMap = do i <- gets snd
                      if (IMap.size newMap < i) then
                        put $ (newMap, IMap.size newMap)
                      else
                        return ()

findClosure from to = 
    if ISet.null from then
      updateMin to
    else
      do bestSize <- gets snd
         if (ISet.size from + IMap.size to >= bestSize) then
           return ()
         else
           let (m, from') = deleteFindMin from
               keysTo = IMap.keysSet to
           in forM_ (required m) $ \(req, descr) ->
                let to' = IMap.insert m descr to
                in findClosure (from' +++ (req \\ keysTo)) to'

closure from = let finder = findClosure from IMap.empty
                   dummyState = (IMap.empty, 100000)
               in fst $ execState finder dummyState

closureList = IMap.assocs . closure . ISet.fromList

printClosure = mapM_ pretty . closureList
  where pretty (n, descr) = putStrLn $ (show n) ++ " = " ++ descr