data Encoding = Multiple Int Char | Single Char deriving (Eq,Show,Ord)
Encoding of run length
encode :: String -> [Encoding] encode inputString =encoding (group inputString)  encoding :: [String] -> [Encoding] -> [Encoding] encoding groupString xs= if (length groupString == 0) then xs else case (head groupString) of ([c]) ->encoding (tail groupString) (xs ++ [Single c]) (x) -> encoding (tail groupString) (xs ++ [Multiple (length x) (head x)])
Decoding of run length
decode :: [Encoding] -> String decode listString = decoding listString  decoding :: [Encoding] -> String -> String decoding inputString xs= if (length inputString == 0) then xs else case (head inputString) of (Single x) ->decoding (tail inputString) (xs++ [x]) (Multiple num x) ->decoding (tail inputString) (xs ++ (replicate num x) )
This is my run length encoding solution, can anyone suggest me a better way to write encoding and decoding functionsAnswer1:
A lot of your code is dedicated to updated an accumulator. You add elements to the tail of that accumulator, and this will have a drastic impact on performance.
The reason this is usually not very efficient is because a list in Haskell
[a] is implemented - at least conceptually - as a <em>linked list</em>. As a result concatenating two lists
l2 together with
l1 ++ l2, will take <em>O(|l1|)</em> time (that is the number of elements in
l1). So that means that if the list already contains 100 elements, adding one extra at the end will require a lot of work.
Another anti-pattern is the use of
tail. Yes these functions can be used, but unfortunately since you do not use pattern matching, it could happen that an empty list is passed, and then
tail will error.
Another problem here is that you use
length on a list. Since sometimes lists in Haskell can have infinite length, the
length call will - if we need it - never ends.
In cases where you have to append at the end of the accumulator, usually we can write the recursion in the tail of a list "cons" we are building. So we can rewrite our program from:
encode :: String -> [Encoding] encode  =  encode (h:t) = ...
The question is now how we can count these values. We can use <a href="http://hackage.haskell.org/package/base-188.8.131.52/docs/Prelude.html#v:span" rel="nofollow"><strong>
span :: (a -> Bool) -> [a] -> ([a],[a])</strong></a>, a function that will - for a given predicate and a list - construct a 2-tuple where the first item contains the prefix of the list where all elements satisfy the predicate, and the second item contains the rest of the list, so we can use this like:
encode :: String -> [Encoding] encode  =  encode (h:t) | nh > 1 = Multiple nh h : tl | otherwise = Single h : tl where (s1, s2) = span (h ==) t nh = 1 + length s1 tl = encode s2
Prelude Data.List> encode "Foobaaar qqquuux" [Single 'F',Multiple 2 'o',Single 'b',Multiple 3 'a',Single 'r',Multiple 3 ' ',Multiple 3 'q',Multiple 3 'u',Single 'x']
For the decoding, we again do not need an accumulator, and can make use of <a href="http://hackage.haskell.org/package/base-184.108.40.206/docs/Prelude.html#v:replicate" rel="nofollow"><strong>
replicate :: Int -> a -> [a]</strong></a>:
decode :: [Encoding] -> String decode  =  decode (Single h:t) = h : decode t decode (Multiple nh h) = replicate nh h ++ decode t
Or we can use a list monad instead:
decode :: [Encoding] -> String decode = (>>= f) where f (Single h) = [h] f (Multiple nh h) = replicate nh h
Prelude Data.List> decode [Single 'F',Multiple 2 'o',Single 'b',Multiple 3 'a',Single 'r',Multiple 3 ' ',Multiple 3 'q',Multiple 3 'u',Single 'x'] "Foobaaar qqquuux"Answer2:
As an extension to <a href="https://stackoverflow.com/users/67579/willem-van-onsem" rel="nofollow">Willem Van Onsem's</a> excellent <a href="https://stackoverflow.com/a/48670039/3058609" rel="nofollow">answer</a>, consider creating the run lengths separately, then combining them together with their letters with
Data.List has the function <a href="https://hackage.haskell.org/package/base-220.127.116.11/docs/Data-List.html#v:group" rel="nofollow">
group</a> (which itself is a specialization of the generic
group = groupby (==)) which breaks strings into homogenous substrings. i.e.:
group "aaabbccccd" = ["aaa", "bb", "cccc", "d"]
Calculating the length of each will give you run-length.
group is implemented exactly the same way as Willem's
import Data.List (group) data Encoding = Multiple Int Char | Single Char deriving (Eq, Show, Ord) encode :: String -> [Encoding] encode xs = zipWith op lengths letters where groups = group xs lengths = map length groups letters = map head groups op :: Int -> Char -> Encoding op 1 = Single op n = Multiple n
This could also be done as one very ugly list comprehension.
encode xs = [ let (n, c) = (length g, head g) in if n == 1 then Single c else Multiple n c | g <- group xs ]Answer3:
encoding function is a functional map. Instead of making your own primitive recursive function just use
Your encoding is reversing the output (
xs ++ [Single c] etc) which is both counter intuitive and computationally expensive. Stop it.
Too many parenthesis, such as on
case (..) of,
if (...) then and the arms of the case
(...) ->. All these are unneeded and clutter the code.
If you type
head chances are you should have pattern matched somewhere instead.
encoding :: String -> [Encoding] encoding = map enc . group -- Point 1, use map which also takes -- care of point 2 and 3. where enc [x] = Single x enc xs@(x:_) = Multiple (length xs) x -- Point 4, patterns not `head` -- Here consider make pattern matches total either via an error call or Maybe type