[Haskell-beginners] Recursion/dynamic programming optimization

[Brandon S. Allbery KF8NH]

On Mar 19, 2010, at 16:41 , ivovnenko wrote:
> w :: Eq a => [a] -> [a] -> Int
> w text str = w' (reverse text) (reverse str)
> w' :: Eq a => [a] -> [a] -> Int
> -- Init
> w' _ [] = 0
> w' [] _ = 0
> -- For one symbol string
> w' text [a] =
>         if head text == a then
>                 w' (tail text) [a] +1
>         else
>                 w' (tail text) [a]

Couple of suggestions here:

 > w' (x:xs) s@[a] = w' xs s + (if x == a then 1 else 0)

> -- General case
> w' text str =
>         if head str == head text then
>                 w' (tail text) (tail str) + w' (tail text) str
>         else
>                 w' (tail text) str

 > w' (x:xs) s@(a:as) =
 >   let next = w' xs s
 >    in if x == a then
 >         w' xs as + next
 >       else
 >         next

This will save some function calls by using pattern matching.   
Combining the common subexpressions probably won't count for much  
except in terms of elegance.

The rest probably comes down to strictness but I'll let more  
knowledgeable people comment on that :)

-- 
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery at kf8nh.com
system administrator [openafs,heimdal,too many hats] allbery at ece.cmu.edu
electrical and computer engineering, carnegie mellon university    KF8NH


-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 195 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/beginners/attachments/20100320/147b0cd3/PGP-0001.bin