Re: [Haskell-cafe] C++

If you're trying to memoize a recursive algorithm with a global array of
previous states, you could use the marvellous MemoTrie package [1]. It lets
you write your algorithm recursively, while getting all the benefits of
memoization! Here's an example with the fibonacci function:

fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = memofib (n - 2) + memofib (n - 1)

memofib :: Int -> Integer
memofib = memo fib

> memofib 113 -- runs in O(n), with (permanent!) memory usage also at O(n).

  - Clark

[1] http://hackage.haskell.org/package/MemoTrie


On Tue, Dec 11, 2012 at 2:59 PM, Serguey Zefirov  wrote:

> This array is for dynamic programming.
>
> You can diagonalize it into a list and use technique similar to the
> Fibonacci numbers.
>
> The resulting solution should be purely declarative.
>
> 2012/12/11 mukesh tiwari :
> > Hello All
> > I am trying to transform this C++ code in Haskell. In case any one
> > interested this is solution of SPOJ problem.
> >
> > #include
> > #include
> > #include
> > using namespace std;
> >
> > int memo[1100][1100] ;
> >
> > int recurse( int h , int a , int cnt , bool flag )
> >     {
> >       if ( h <= 0 || a <= 0 ) return cnt ;
> >       if ( memo[h][a] ) return memo[h][a] ;
> >       if ( flag ) memo[h][a] =  recurse ( h + 3 , a + 2 , cnt + 1 ,
> !flag )
> > ;
> >       else
> >          memo[h][a] = max ( memo[h][a] ,  max ( recurse ( h - 5 , a - 10
> ,
> > cnt + 1 , !flag ) , recurse ( h - 20 , a + 5 , cnt + 1 , !flag ) ) ) ;
> >
> >      return memo[h][a];
> >    }
> >
> > int main()
> >   {
> >     int n , a , b ;
> >     scanf( "%d", &n );
> >     for(int i = 0 ; i < n ; i++)
> >     {
> >      memset ( memo , 0 , sizeof memo ) ;
> >      scanf("%d%d", &a , &b );
> >      printf("%d\n" , recurse( a , b , -1 ,  1 ));
> >      if( i != ( n - 1 ) ) printf("\n");
> >     }
> >
> >   }
> >
> > I am stuck with that memo[1100][1100] is global variable so I tried to
> solve
> > this problem using state monad ( Don't know if its correct approach or
> not )
> > but it certainly does not seem correct to me. Till now I came up with
> code.
> > Could some one please tell me how to solve this kind of problem (
> Generally
> > we have a global variable either multi dimensional array or map  and we
> > store the best values found so far in the table ).
> >
> > import qualified Data.Map.Strict as SM
> > import Control.Monad.State
> >
> > {--
> > funsolve_WF :: Int -> Int -> Int -> Int
> > funsolve_WF h a cnt
> >      | h <= 0 || a <= 0 = cnt
> >      | otherwise = funsolve_Air h a ( cnt + 1 )
> >
> > funsolve_Air :: Int -> Int -> Int -> Int
> > funsolve_Air h a cnt = max ( funsolve_WF ( h + 3 - 5 ) ( a + 2 - 10 )
> cnt' )
> > ( funsolve_WF ( h + 3  - 20 )  ( a + 2  + 5 )  cnt' ) where
> >                       cnt' = cnt + 1
> > --}
> >
> >
> >
> > funSolve :: Int -> Int -> Int -> Bool -> State ( SM.Map ( Int , Int )
>  Int )
> > Int
> > funSolve hl am cnt f
> >     | hl <= 0 && am <= 0 = return cnt
> >     | otherwise = do
> >             mp <- get
> >             case () of
> >                _| SM.member ( hl , am ) mp -> return  mp SM.! ( hl , am )
> >                 | f -> do
> >                       --here I have to insert the value return by
> function
> > funSolve ( hl + 3 ) ( am + 2 ) (  cnt + 1 )  ( not f ) to map whose key
> is (
> > hl , am )
> >                         let k = evalState ( funSolve ( hl + 3 ) ( am + 2
> )
> > ( cnt + 1 ) ( not f ) ) mp
> >                         modify ( SM.insert ( hl , am ) k )
> >
> >
> >                 | otherwise ->  do
> >                        do
> >                         let k_1 = evalState ( funSolve ( hl - 5 )  ( am
> - 10
> > )  ( cnt + 1 ) ( not f  ) ) mp
> >                             k_2 = evalState ( funSolve ( hl - 20 ) ( am
> + 5
> > )  ( cnt + 1 ) ( not f  ) ) mp
> >                             k_3 =  mp SM.! ( hl , am )
> >                         modify ( SM.insert ( hl , am )  ( maximum [ k_1 ,
> > k_2 , k_3 ] )  )
> >
> > Regards
> > Mukesh Tiwari
> >
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe@haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>