0votos

Min and Second Min en Haskell

por josejuan hace 5 años

Como un monoide, con coste O(n) y genéricamente paralelizable a O(n/p).

Escribir la función min_element_1st_2nd(S) que retorne el par de elementos (f, s) dado que f sea el menor elemento de la secuencia y s sea el segundo menor elemento de la secuencia.

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import Data.Maybe 
import Data.Monoid 
 
{- 
 
 En cuanto a la eficiencia, claramente puede resolverse en O(n/p), una forma genérica 
 de definir esa solución es usar un monoide, que es inherentemente paralelizable. 
  
 Sea S el conjunto de las soluciones formadas por los dos posibles valores que son 
 los dos primeros elementos de menor valor (que no mínimos) en una secuencia (alterando 
 el orden si uno de ellos es estrictamente menor que el otro). 
  
 Entonces, puede definirse el monoide (no conmutativo) en S como: 
 
-} 
 
join_lowers :: (a -> a -> Bool) -> (Maybe a, Maybe a) -> (Maybe a, Maybe a) -> (Maybe a, Maybe a) 
join_lowers isLessThan a b = 
  case (a, b) of 
  (u, (Nothing, _)) -> u 
  ((Nothing, _), u) -> u 
  ((x, Nothing), (r, Nothing)) -> if r `isLessThan'` x then (r, x) else (x, r) 
  ((x, Nothing), (r, s)) -> if r `isLessThan'` x then (r, s `isBetterThan` x) else (x, r) 
  ((x, y), (r, Nothing)) -> if r `isLessThan'` x then (r, x) else (x, r `isBetterThan` y) 
  ((x, y), (r, s)) -> if s `isLessThan'` x then (r, s) else if r `isLessThan'` x then (r, x) else (x, r `isBetterThan` y) 
 
  where (Just p) `isLessThan'` (Just q) = p `isLessThan` q 
        p `isBetterThan` q = if p `isLessThan'` q then p else q 
 
 
{- 
 
  El elemento neutro del monoide sería: 
 
-} 
empty_lowers = (Nothing, Nothing) 
 
 
{- 
 
  Meter un elemento de un conjunto en nuestro monoide sería: 
 
-} 
return_lowers x = (Just x, Nothing) 
 
{- 
 
  Y la operación de reducir una secuencia bajo dicho monoide sería 
 
-} 
 
first_two_lowers' :: (a -> a -> Bool) -> [a] -> (Maybe a, Maybe a) 
first_two_lowers' isLessThan = foldl (join_lowers isLessThan) empty_lowers . map return_lowers 
 
-- Con coste O(n) 
 
------------------------------------------------------- 
-- En Haskell, puede definirse un monoide como 
 
data Lowers a = Lowers (Maybe a, Maybe a) 
 
instance Ord a => Monoid (Lowers a) where 
  mempty  = Lowers empty_lowers 
  (Lowers a) `mappend` (Lowers b) = Lowers $ join_lowers (<) a b 
   
-- El cual, puede paralelizarse para obtener O(n/p), por ejemplo 
-- como en http://www.solveet.com/exercises/Factorizar-el-factorial/243/solution-1656 
 
------------------------------------------------------- 
-- Un ejemplo de uso del monoide anterior podría ser 
 
data MyData = MyData Int String deriving (Eq, Show) 
 
instance Ord MyData where 
  (MyData x _) <= (MyData y _) = x <= y 
 
lowersFromMyData = map (Lowers . return_lowers) 
 
-- Así, reducir bajo el monoide sería: 
test = 
 
   mconcat $ lowersFromMyData [ MyData 5 "Pepe" 
                              , MyData 3 "Juan" 
                              , MyData 1 "Luis" 
                              , MyData 4 "Tomas" 
                              , MyData 2 "Carlos" 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.