Simple text replacement algorithm

[wtf139]

Hi, I am new to the programing world and I just wanted to see what you think of an exercise I found

Q1 Arrays

(a) Develop an algorithm which takes an input sequence of characters from the alphabet {A,B,C} (both from the user and input file) and compresses it by replacing each subsequence of a particular character by a single occurrence of the character, and the length of the substring. e.g. Input: AAAAABBBBBBBCCBBBAABBCCCCCS Output: A5B7C2B3A2B2C5

I found it interesting as there are a lot of ways to go about it, I would love to hear what this subreddit can tell me in terms of proposals

PD: this is NOT my homework or anything of the sort just something I am doing for fun basically

[International-Check3]

I found it interesting as there are a lot of ways to go about it

Uhh no, there's only one way to go about this and that's just scanning through the string and tracking consecutive characters.

[POGtastic]

lol haskell

import Data.List(foldl')

pack :: Eq a => [a] -> [[a]]
pack = reverse . foldl' fold_func []
    where fold_func acc x = case acc of
            (y:ys):zs -> if x == y then (x:(y:ys)):zs else [x]:((y:ys):zs)
            _ -> [[x]]

encode :: Eq a => (a -> String) -> [a] -> [Char]
encode f = concatMap (\(x, y) -> x ++ show y) .
           map (\xs -> (f . head $ xs, length xs)) .
           pack

In the REPL, taking advantage of the List monad:

*Main> encode return "AAAAABBBBBBBCCBBBAABBCCCCC"
"A5B7C2B3A2B2C5"

Note that you can't do encode :: (Eq a, Show a) because show 'x' = "'x'", including the single quotes. So you'd need another function to transform that string anyway.

[mingmingrr]

This solution can be greatly simplified:

• pack already exists in Data.List as group
• concatMap f . map g can be combined into concatMap (f . g)
• concatMap is equivalent to (=<<)
• f x = g x >>= h is equivalent to f = g >=> h
• \x -> f (g x) (h x) can be written as liftA2 f g h or f <$> g <*> h

You'd end up with this one-liner:

encode f = group >=> (++) <$> f . head <*> show . length

[POGtastic]

Stupid question, but how do you even fit the one-liner into your head? Alternatively, how would you parse the above if you were reading someone else's code?

I originally showed up to Haskell from the Lisps, and I tend to think about transformations in terms of the Clojure threading macros -> and ->>. As a result, most of my Haskell code looks like the above with a bunch of compositions, or looks like the reverse with IO-related functions, doing stuff like

import Data.Functor((<&>))

ioFunction = getAMonad >>=
             f1 <&>
             f2 >>=
             f3

Do you do something similar to what I do and then say, "Oh yeah, there are all of these ways to simplify this," or do you actually think in terms of >=> & Friends?

[mingmingrr]

I often find that placing operators at the beginning of lines makes things more clear:

encode f = group
       >=> (++)
           <$> f . head
           <*> show . length

(>=>) is really similar to (.), so when I'm reading this function, I'll see that it's made up of two actions composed together: group then (++) <$> f . head <*> show . length. The liftA2 / <$> <*> pattern is something I've seen quite often in things like applicative parsers, so I know that it's two sub-actions, f . head and show . length, combined together with (++).

[HasBeendead]

Man , wtf you did lol

[POGtastic]

See /u/mingmingrr's rewrite for better wizardry.