0votos

Are they Same? en Haskell

por josejuan hace 11 días

Se comparan cuatro implementaciones diferentes.

La Kata Are they same? consiste en comparar dos arrays de enteros a y b, de forma que los elementos de b, deben de ser el cuadrado de los elementos de a. Los elementos de ambas listas no tienen porque tener el mismo orden dentro los arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
{-# LANGUAGE TupleSections #-} 
import System.Environment 
import qualified Data.IntSet as Set 
import qualified Data.IntMap.Strict as Map 
import Data.List (sort) 
import Data.Function 
import Control.Arrow 
import Data.Array.ST 
import Data.Array.Unboxed 
import Control.Monad.ST 
import Control.Monad 
 
comp1 = ((==) `on` sort) . map (^2) 
 
comp3 xs = let s = Set.fromList $ map (^2) xs 
           in  all (`Set.member` s) 
 
comp2 = less . more 
  where more = Map.fromListWith (+) . map ((,1) . (^2)) 
        less m    []  = Map.null m 
        less m (x:xs) = case Map.lookup x m of 
                          Just 1  -> less (Map.delete              x m) xs 
                          Just n  -> less (Map.adjust (subtract 1) x m) xs 
                          Nothing -> False 
 
comp4 :: Int -> [Int] -> [Int] -> Bool 
comp4 m xs ys = runST $ do 
  v <- newArray (0, m^2) 0 :: ST s (STUArray s Int Int) 
  forM_ (map (,-1) ys ++ map ((,1).(^2)) xs) $ \(i, d) -> 
    readArray v i >>= writeArray v i . (+d) 
  ((0 ==) . sum) <$> getElems v 
 
ts f = [(a, b) | (a, b, r) <- xs, f b a /= r] 
 where xs = [([], [0], False) 
            ,([], [], True) 
            ,([1], [1], True) 
            ,([4], [2], True) 
            ,([4, 4], [2], False) 
            ,([4], [2, 2], False) 
            ,([4, 4], [2, 2], True) 
 
test = mapM_ print $ filter (not . null . snd) $ map (second ts) 
  [("comp1", comp1) 
  ,("comp2", comp2) 
  ,("comp3", comp3) 
  ,("comp4", comp4 5) 
 
main = do 
  (t:n:_) <- map read <$> getArgs 
  let xs = take n $ cycle [1..100] 
      ys = map (^2) xs 
      f  = case t of 
             1 -> comp1 
             2 -> comp2 
             3 -> comp3 
             4 -> comp4 100 
  print $ f xs ys 
 
{- 
 
[josejuan@centella centella]$ for i in `seq 1 4`; do echo "comp$i: `time -f "%E, %M" ../dif1 $i 10000000 2>&1`"; done 
comp1: True 
0:39.02, 1903624 
comp2: True 
0:05.39, 491600 
comp3: True 
0:03.48, 587804 
comp4: True 
0:01.29, 297832 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.