<br>Hi,<br> I am a student and we had an
assignment in Haskell. The question, was given a string of the form
"1-2+3*5-7+4-6+3" i.e., any sequence of integers as well as some
operators between them we had to find a maximum possible value for the
expression as well as the expression itself . So for maxval
"1-2+3*5-7+4-6+3" it is (76,"(1-((2+3)*((5-(7+4))-(6+3))))"). The
function we had to write was maxval :: String -> (Int,String). For
further details on the question, have a look at <a href="http://www.cmi.ac.in/%7Emadhavan/courses/programming08/assignment6.txt" target="_blank">our sir's web page here</a>.
I solved the question, we had to use memoization, and submitted the
solution. It is given below. Now the problem is I am just wondering if
it can be solved in a better manner. Translation : Is there some way in
Haskell to do it in a more simpler way and as well as to reduce the
number of lines of the program.<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">{-<br>---------------------------------------------------------------------------------------------------------------------------<br>
*********************** module Memo.hs ******************************************************<br>
---------------------------------------------------------------------------------------------------------------------------<br>
-}<br>module Memo(Table,emptytable,memofind,memolookup,memoupdate,memoupdateArray) where<br><br>data (Eq a) => Table a b c = T [(a,a,(b,c),(b,c))]<br> deriving (Eq,Show)<br><br>emptytable :: (Eq a) => (Table a b c)<br>
emptytable = T []<br><br>memofind :: (Eq a) => (Table a b c) ->(a,a)-> Bool<br>memofind (T []) _ = False<br>memofind (T ((y,z,(v1,s1),(v2,s2)):l)) x<br> | x == (y,z) = True<br> | otherwise = memofind (T l) x<br>
<br>memolookup :: (Eq a) => (Table a b c) -> (a,a) -> ((b,c),(b,c))<br>memolookup (T ((y,z,(v1,s1),(v2,s2)):l)) x<br> | x == (y,z) = ((v1,s1),(v2,s2))<br> | otherwise = memolookup (T l) x<br><br>memoupdate :: (Eq a) => (Table a b c) -> (a,a,(b,c),(b,c)) -> (Table a b c)<br>
memoupdate (T l) x = T (x:l)<br><br>memoupdateArray :: (Eq a) => (Table a b c) -> [(a,a,(b,c),(b,c))] -> (Table a b c)<br>memoupdateArray t [] = t<br>memoupdateArray t (x:xs) = memoupdate (memoupdateArray t xs) x<br>
<br>{-<br>---------------------------------------------------------------------------------------------------------------------------<br>***********************End of module Memo.hs***********************************************<br>
---------------------------------------------------------------------------------------------------------------------------<br>-}<br><br><br>{-<br>---------------------------------------------------------------------------------------------------------------------------<br>
******************The actual program , assign-6.hs******************************************<br>
---------------------------------------------------------------------------------------------------------------------------<br>
-}<br><br>minArray :: [(Int,String)] -> (Int,String)<br>minArray ((x,expr):[]) = (x,expr)<br>minArray ((x,expr):l) |((min x (fst (minArray l))) ==x) = (x,expr)<br> |otherwise = (minArray l)<br>
<br>maxArray :: [(Int,String)] -> (Int,String)<br>maxArray ((x,expr):[]) = (x,expr)<br>maxArray ((x,expr):l) |((max x (fst (minArray l))) ==x) = (x,expr)<br> |otherwise = (minArray l)<br>
<br>import Memo<br>import Char<br><br>type Tuple = (Int,Int,(Int,String),(Int,String))<br><br>maxval :: String ->(Int, String) <br>maxval expr = snd (memolookup (buildmemo expr 1 emptytable) (1,length expr))<br><br>initmemo :: (String) -> (Table Int Int String)<br>
initmemo expr = (memoupdateArray (emptytable) <br> [(i,i,(toInt(expr!!(i-1)),[expr!!(i-1)]),<br> (toInt(expr!!(i-1)),[expr!!(i-1)]))|i<-[1..length expr],j<-[0,1],i `mod` 2 ==1])<br>
<br>buildmemo :: (String)->Int -> (Table Int Int String)-> (Table Int Int String)<br>buildmemo expr col memo | (col > length expr) = memo<br> | (col == 1) = buildmemo expr 3 (memoupdateArray (emptytable) <br>
[(i,i,(toInt(expr!!(i-1)),[expr!!(i-1)]),<br> (toInt(expr!!(i-1)),[expr!!(i-1)]))|i<-[1..length expr],i `mod` 2 ==1])<br> | otherwise = buildmemo expr (col+2) (memoupdateArray (memo) (createList expr memo (1,col)))<br>
<br>createList :: String-> (Table Int Int String) -> (Int,Int) -> [Tuple]<br>createList expr memo (i,j) | j > (length expr) = []<br> | otherwise = (i,j,min_expr,max_expr):(createList expr memo (i+2,j+2))<br>
where<br> min_expr = minArray [x | (x,y) <- list]<br> max_expr = maxArray [y | (x,y) <- list]<br> list = [(compute memo (i,k) (k+2,j) (expr!!k))|k<-[i..j-2],k `mod` 2 ==1]<br>
<br>compute :: (Table Int Int String)->(Int,Int)->(Int,Int)->Char->((Int,String),(Int,String))<br>compute memo (x1,x2) (y1,y2) op |op == '+' = ((min1+min2,"("++min1_expr++"+"++min2_expr++")"),<br>
(max1+max2,"("++max1_expr++"+"++max2_expr++")"))<br> |op == '-' = ((min1-max2,"("++min1_expr++"-"++max2_expr++")"),<br>
(max1-min2,"("++max1_expr++"-"++min2_expr++")")) <br> |op == '*' = (minArray xs,maxArray xs)<br> where<br> xs = [(min1*min2,"("++min1_expr++"*"++min2_expr++")"),<br>
(min1*max2,"("++min1_expr++"*"++max2_expr++")"),<br> (max1*min2,"("++max1_expr++"*"++min2_expr++")"),<br> (max1*max2,"("++max1_expr++"*"++max2_expr++")")]<br>
((min1,min1_expr),(max1,max1_expr)) = (memolookup memo (x1,x2))<br> ((min2,min2_expr),(max2,max2_expr)) = (memolookup memo (y1,y2))<br><br>minArray :: [(Int,String)] -> (Int,String)<br>
minArray ((x,expr):[]) = (x,expr)<br>minArray ((x,expr):l) |((min x (fst (minArray l))) ==x) = (x,expr)<br> |otherwise = (minArray l)<br><br>maxArray :: [(Int,String)] -> (Int,String)<br>maxArray ((x,expr):[]) = (x,expr)<br>
maxArray ((x,expr):l) |((max x (fst (maxArray l))) ==x) = (x,expr)<br> |otherwise = (maxArray l)<br><br>toInt :: Char -> Int<br>toInt x = ord x - ord '0'<br><br>{-<br>---------------------------------------------------------------------------------------------------------------------------<br>
***********************End of program assign-6.hs*******************************************<br>
---------------------------------------------------------------------------------------------------------------------------<br>-}</blockquote>