[Haskell-beginners] editing a list

[Daniel Fischer]

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