Dynamic programming with string keys in Haskell

Question

Being rather new to pure functional programming idiom, I can't get how to implement this case of dynamic programming. I have a function f :: String -> [String] which is calculated recursively and want to memoize it. Input Strings can be arbitrary, so I guess that something like a lazy Map is needed, but couldn't find any. How to implement such case in Haskell?

Have you looked on Hackage? There's about a dozen memoization libraries available... — Daniel Wagner
– Daniel Wagner, Commented Oct 14, 2012 at 9:32

luqui · Accepted Answer · 2012-10-15 17:54:23Z

1

Use a memoizer library:

import qualified Data.MemoCombinators as Memo

f :: String -> [String]
f = Memo.list Memo.char memof  -- because String = [Char]
    where
    memof x = ... f ...          -- call *f* recusively (not memof)

See the documentation for more. Also see MemoTrie

edited Oct 15, 2012 at 17:54

answered Oct 15, 2012 at 0:31

luqui

60.7k12 gold badges153 silver badges210 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

aplavin Over a year ago

I didn't think that it's implemented as an external library and didn't search search at hackage. And it seems strange that such functions are not in the default GHC libraries.

Collectives™ on Stack Overflow

Dynamic programming with string keys in Haskell

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related