LZW compression: Difference between revisions

Line 2,036:

<lang Haskell>import Data.List (elemIndex, tails)

import Control.Applicative (liftA2)

import Data.Maybe (fromJust)

⚫

take2 :: [a] -> [[a]]

⚫

take2 xs = filter ((2 ==) . length) (take 2 <$> tails xs)

doLZW :: String -> String -> [Int]

Line 2,059:

Line 2,055:

(!!)

(foldl

(~~liftA2~~

((.) <$> (++) <*>

⚫

(\x xs -> return (((++) <$> head <*> take 1 . last) ((x !!) <$> xs))))

(.)

(++)

⚫

(\x xs -> return (~~liftA2~~ (++) head (take 1 . last) ((x !!) <$> xs))))

(return <$> a)

(take2 cs))~~</lang>~~

(take2 cs))

⚫

take2 :: [a] -> [[a]]

Testing:

⚫

take2 xs = filter ((2 ==) . length) (take 2 <$> tails xs)

⚫

~~<lang~~ ~~Haskell>*Main>~~ doLZW ['\0'..'\255'] "TOBEORNOTTOBEORTOBEORNOT"

⚫

[84,79,66,69,79,82,78,79,84,256,258,260,265,259,261,263]

main :: IO ()

⚫

*Main> ~~undoLZW~~ ~~['\0'..'\255']~~ [84,79,66,69,79,82,78,79,84,256,258,260,265,259,261,263]

main = do

⚫

"TOBEORNOTTOBEORTOBEORNOT"</lang>

⚫

print $ doLZW ['\0' .. '\255'] "TOBEORNOTTOBEORTOBEORNOT"

Encode --> decode --> compare with original text.

print $

<lang Haskell>*Main> (ap (==) . liftM2 (.) undoLZW doLZW) ['\0'..'\255'] "TOBEORNOTTOBEORTOBEORNOT"

undoLZW

⚫

True</~~lang~~>

['\0' .. '\255']

⚫

[84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258, 260, 265, 259, 261, 263]

print $

((==) <*> ((.) <$> undoLZW <*> doLZW) ['\NUL' .. '\255'])

⚫

"TOBEORNOTTOBEORTOBEORNOT"</lang>

⚫

<pre>[84,79,66,69,79,82,78,79,84,256,258,260,265,259,261,263]

"TOBEORNOTTOBEORTOBEORNOT"

⚫

True</pre>

Other (elegant) code can be found at Haskell wiki [http://www.haskell.org/haskellwiki/Toy_compression_implementations Toy compression]