On Saturday 30 October 2010 16:59:00, Jonathan Phillips wrote:
I have a list (more precisely a string) which I'm trying to recurse through, editing sections as I come to it. It's obvious how to do it with a for loop, but I'm doing it all wrong in haskell, as this simple task is running mind-numbingly slowly.
addOneNum cycles through each line, and when it gets to character 23, it calls changeNo, which edits the string. The problem is clearly the adding on to the end of the string,
Yes, that's bad, since the parentheses nest the wrong way. You get ((((a ++ b) ++ c) ++ d) ++ e) and to get to the start, you have to dig through all those layers of parentheses. It would be less bad if the construction built right-nested parentheses.
but the only other way I can see of doing it is writing the 'new string' backwards and then reverse it at the end. This looks like it would make the function even less legible than it already is though.
It's a fairly common technique, since consing to the front of a list is very cheap while appending to the end is expensive (especially if you repeatedly add single elements). However, here you can get much better behaviour by using another common technique, delivering the string incrementally. Since all you ever do with the accumulator is appending to the end of it, you don't need an accumulator at all.
addOneNum :: String -> String -> Integer -> String
addOneNum x [] _ = x addOneNum x (y:ys) n = case n of 23 -> changeNo x (y:ys) n _ -> case y of '\n' -> addOneNum (x ++ [y]) ys 1 _ -> addOneNum (x ++ [y]) ys (n+1)
addOneNum' :: String -> Integer -> String addOneNum' [] _ = [] addOneNum' (y:ys) n = case n of 23 -> changeNo' (y:ys) n _ -> case y of '\n' -> y : addOneNum' ys 1 _ -> y : addOneNum' ys (n+1) changeNo' :: String -> Integer -> String changeNo' (w:x:y:z:xs) n = let s = show ((read [w,x,y,z] :: Integer) + 1) in case length s of 0 -> " " ++ addOneNum' xs (n+4) -- can't happen, by the way l | l < 4 -> s ++ " " ++ addOneNum' xs (n+4) -- guessing it's the same number of spaces for those | otherwise -> error "asdf" changeNo' _ _ = error "changeNo' error" If the input is incrementally produced and the output sequentially consumed, that runs in constant space (and if not all output is needed, it'll stop early).
changeNo :: String -> String -> Integer -> String changeNo v (w:x:y:z:xs) n = case length(show((read([w,x,y,z])::Integer) + 1)) of 0 -> addOneNum (v ++ " ") xs (n+4) 1 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ " ") xs (n+4) 2 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ " ") xs (n+4) 3 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ " ") xs (n+4) 4 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1)) xs (n+4) _ -> error "asdf" changeNo w _ n = error "changeNo error"
Also, while I'm at it, it looks like I want to be using an as-pattern (or some C-style #define thing):
changeNo v (w:x:y:z:xs) n = case length(s@(show((read([w,x,y,z])::Integer) + 1))) of 0 -> addOneNum (v ++ " ") xs (n+4) 1 -> addOneNum (v ++ s ++ " ") xs (n+4) 2 -> addOneNum (v ++ s ++ " ") xs (n+4) 3 -> addOneNum (v ++ s ++ " ") xs (n+4) 4 -> addOneNum (v ++ s) xs (n+4) _ -> error "asdf"
but that gives me a 'not in scope' error. Any suggestions?
You can use as-patterns only in pattern-matching contexts. You could write case show (...) of s -> case length s of 0 -> ... but normally you bind the value to the name via a let (or where).
Cheers, PhiJ