hpaste

module Main where

import Control.Monad

-- Run length Encoding
-- Output is a list of triples of the form (value, startpos, run length)
encode_acc :: Eq a => [a] -> Int -> [(a, Int, Int)] -> [(a, Int, Int)]
encode_acc [] i accs = accs
encode_acc (x:xs) i [] = encode_acc xs (i+1) [(x, i, 1)]
encode_acc (x:xs) i (this@(val, sp, rl):accs)
    | x == val = encode_acc xs (i+1) ((val, sp, rl+1):accs)
    | otherwise = encode_acc xs (i+1) ((x, i, 1):this:accs)

-- Take the raw input list and do the stuff and then reverse it
encode :: Eq a => [a] -> [(a, Int, Int)]
encode lst = reverse $ encode_acc lst 0 []

-- Make up some fake data
genfake = concatMap $ uncurry replicate
fake = genfake [(20000, 1), (15555, 2), (13000, 1), (99999, 2), (10000, 3), (10000, 9),
    (22222, 1), (33333, 3), (25000, 5), (30000, 1), (1, 2),
    (35000, 3), (65000, 2), (100000, 10), (50000, 1), (75000, 2),
    (100000, 5), (100000, 2), (250000, 3), (100000, 1),
    (500000, 4), (500000, 1), (250000, 1), (500000, 2)]


main = do
    let encoded = encode fake
    mapM_ print encoded
    return ()

{-# LANGUAGE BangPatterns #-}

import Control.Monad

data T a = T !a {-# UNPACK #-} !Int {-# UNPACK #-} !Int
    deriving Show

data P a = P !a !a

-- Run length Encoding
-- Output is a list of triples of the form (value, startpos, run length)
encode_acc :: Eq a => [a] -> Int -> [T a] -> [T a]
encode_acc [] !i accs = accs
encode_acc (x:xs) i [] = encode_acc xs (i+1) [T x i 1]
encode_acc (x:xs) i (this@(T val sp rl):accs)
    | x == val  = encode_acc xs (i+1) (T val sp (rl+1) : accs)
    | otherwise = encode_acc xs (i+1) ((T x i 1):this:accs)

-- Take the raw input list and do the stuff and then reverse it
encode :: Eq a => [a] -> [T a]
encode lst = reverse $ encode_acc lst 0 []

-- Make up some fake data
genfake = concatMap $ uncurry replicate

fake :: [Int]
fake = genfake [(20000, 1), (15555, 2), (13000, 1), (99999, 2), (10000, 3), (10000, 9),
                (22222, 1), (33333, 3), (25000, 5), (30000, 1), (1, 2),
                (35000, 3), (65000, 2), (100000, 10), (50000, 1), (75000, 2),
                (100000, 5), (100000, 2), (250000, 3), (100000, 1),
                (500000, 4), (500000, 1), (250000, 1), (500000, 2)]

main = mapM_ print (encode fake)



{-

$ ghc -O2 A.hs

$ time ./A
T 1 0 20000
T 2 20000 15555
T 1 35555 13000
T 2 48555 99999
T 3 148554 10000
T 9 158554 10000
T 1 168554 22222
T 3 190776 33333
T 5 224109 25000
T 1 249109 30000
T 2 279109 1
T 3 279110 35000
T 2 314110 65000
T 10 379110 100000
T 1 479110 50000
T 2 529110 75000
T 5 604110 100000
T 2 704110 100000
T 3 804110 250000
T 1 1054110 100000
T 4 1154110 500000
T 1 1654110 750000
T 2 2404110 500000
./A  0.12s user 0.00s system 89% cpu 0.134 total

{-# LANGUAGE BangPatterns #-}

import Control.Monad

data T a = T !a {-# UNPACK #-} !Int {-# UNPACK #-} !Int
    deriving Show

-- Run length Encoding
-- Output is a list of triples of the form (value, startpos, run length)
encodeAcc :: Eq a => [a] -> Int -> T a -> [T a]
encodeAcc []    !i  t = [t]
encodeAcc (x:xs) i (this@(T val sp rl))
    | x == val  = encodeAcc xs (i+1) (T val sp (rl+1))
    | otherwise = this:encodeAcc xs (i+1) (T x i 1)

-- Take the raw input list and do the stuff and then reverse it
encode :: Eq a => [a] -> [T a]
encode []     = []
encode (x:xs) = encodeAcc xs 1 (T x 0 1)

-- Make up some fake data
genfake = concatMap $ uncurry replicate

fake :: [Int]
fake = genfake [(20000, 1), (15555, 2), (13000, 1), (99999, 2), (10000, 3), (10000, 9),
                (22222, 1), (33333, 3), (25000, 5), (30000, 1), (1, 2),
                (35000, 3), (65000, 2), (100000, 10), (50000, 1), (75000, 2),
                (100000, 5), (100000, 2), (250000, 3), (100000, 1),
                (500000, 4), (500000, 1), (250000, 1), (500000, 2)]

main = mapM_ print (encode fake)

import Control.Monad

data T a = T !a {-# UNPACK #-} !Int {-# UNPACK #-} !Int
    deriving Show

-- Run length Encoding
-- Output is a list of triples of the form (value, startpos, run length)
encodeAcc :: Eq a => [a] -> Int -> T a -> [T a]
encodeAcc []     !i  t = [t]
encodeAcc (x:xs) !i (this@(T val sp rl))
    | x == val  = encodeAcc xs (i+1) (T val sp (rl+1))
    | otherwise = this:encodeAcc xs (i+1) (T x i 1)

-- Take the raw input list and do the stuff and then reverse it
encode :: Eq a => [a] -> [T a]
encode []     = []
encode (x:xs) = encodeAcc xs 1 (T x 0 1)

-- Make up some fake data
genfake = concatMap $ uncurry replicate

fake :: [Int]
fake = genfake [(20000, 1), (15555, 2), (13000, 1), (99999, 2), (10000, 3), (10000, 9),
                (22222, 1), (33333, 3), (25000, 5), (30000, 1), (1, 2),
                (35000, 3), (65000, 2), (100000, 10), (50000, 1), (75000, 2),
                (100000, 5), (100000, 2), (250000, 3), (100000, 1),
                (500000, 4), (500000, 1), (250000, 1), (500000, 2)]

main = mapM_ print (encode fake)

{-# LANGUAGE BangPatterns #-}

import Control.Monad

data T a = T !a {-# UNPACK #-} !Int {-# UNPACK #-} !Int
    deriving Show

-- Run length Encoding
-- Output is a list of triples of the form (value, startpos, run length)
encodeAcc :: Eq a => [a] -> Int -> T a -> [T a]
encodeAcc []     !i  t = [t]
encodeAcc (x:xs) !i  (this@(T val sp rl))
    | x == val  = encodeAcc xs (i+1) (T val sp (rl+1))
    | otherwise = this : encodeAcc xs (i+1) (T x i 1)

-- Take the raw input list and do the stuff and then reverse it
encode :: Eq a => [a] -> [T a]
encode []     = []
encode (x:xs) = encodeAcc xs 1 (T x 0 1)

-- Make up some fake data
genfake = concatMap $ uncurry replicate

fake :: [Int]
fake = genfake [(20000, 1), (15555, 2), (13000, 1), (99999, 2), (10000, 3), (10000, 9),
                (22222, 1), (33333, 3), (25000, 5), (30000, 1), (1, 2),
                (35000, 3), (65000, 2), (100000, 10), (50000, 1), (75000, 2),
                (100000, 5), (100000, 2), (250000, 3), (100000, 1),
                (500000, 4), (500000, 1), (250000, 1), (500000, 2)]

main = mapM_ print (encode fake)


{-

$ time ./B
T 1 0 20000
T 2 20000 15555
T 1 35555 13000
T 2 48555 99999
T 3 148554 10000
T 9 158554 10000
T 1 168554 22222
T 3 190776 33333
T 5 224109 25000
T 1 249109 30000
T 2 279109 1
T 3 279110 35000
T 2 314110 65000
T 10 379110 100000
T 1 479110 50000
T 2 529110 75000
T 5 604110 100000
T 2 704110 100000
T 3 804110 250000
T 1 1054110 100000
T 4 1154110 500000
T 1 1654110 750000
T 2 2404110 500000
./B  0.13s user 0.00s system 99% cpu 0.131 total

$s$wencodeAcc :: [Int]
                      -> Int#
                      -> Int#
                      -> Int#
                      -> Int#
                      -> [T Int]

-}

Lazy:

$s$wencodeAcc =
  \ (xs_a81 :: [Int])
    (x_axe :: Int#)
    (ww_sIS :: Int#)
    (sc_sNx :: Int#)
    (sc1_sNy :: Int#) ->
    case xs_a81 of wild_B1 {
      [] ->
        :
          @ (T Int)
          (T @ Int (I# x_axe) ww_sIS sc_sNx)
          ([] @ (T Int));
      : x1_a80 xs1_X8k ->
        case x1_a80 of wild1_axc { I# x2_Xxz ->
        case ==# x2_Xxz x_axe of wild2_XK {
          False ->
            :
              @ (T Int)
              (T @ Int (I# x_axe) ww_sIS sc_sNx)
              ($s$wencodeAcc xs1_X8k x2_Xxz sc1_sNy 1 (+# sc1_sNy 1));
          True ->
            $s$wencodeAcc
              xs1_X8k x_axe ww_sIS (+# sc_sNx 1) (+# sc1_sNy 1)
        }
        }


Tail recursion:

$s$wencode_acc :: [T]
                       -> [Int]
                       -> Int#
                       -> Int#
                       -> Int#
                       -> Int#
                       -> [T]

$s$wencode_acc =
  \ (wild_XY :: [T])
    (xs_a7U :: [Int])
    (x_awy :: Int#)
    (ww_sHR :: Int#)
    (sc_sMA :: Int#)
    (sc1_sMB :: Int#) ->
    case xs_a7U of wild1_B1 {
      [] -> : @ T (T x_awy ww_sHR sc_sMA) wild_XY;
      : x1_a7T xs1_X86 ->
        case x1_a7T of wild2_aww { I# x2_XwM ->
        case ==# x2_XwM x_awy of wild3_X19 {
          False ->
            $s$wencode_acc
              (: @ T (T x_awy ww_sHR sc_sMA) wild_XY)
              xs1_X86
              x2_XwM
              sc1_sMB
              1
              (+# sc1_sMB 1);
          True ->
            $s$wencode_acc
              wild_XY xs1_X86 x_awy ww_sHR (+# sc_sMA 1) (+# sc1_sMB 1)
        }
        }

Powered by HAppS. Copyright (c) 2007 glguy @ #haskell. Source via darcs.