0votos

Min and Second Min en Haskell

por josejuan hace 3 años

El enunciado es ambiguo. No es lo mismo dos elementos mínimos que dos elementos con el menor valor posible. En el primer caso, los elementos deben ser minimales y en segundo no. Aquí se resuelve ambas versiones *sin usar igualdad*, únicamente una relación de orden (ej. "menor que").

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
-- Encuentra dos elementos minimales en orden en la secuencia 
first_two_minimals :: (a -> a -> Bool) -> [a] -> [a] 
first_two_minimals isLessThan set = take 2 $ filter (\x -> not $ any (`isLessThan` x) set) set 
 
{- 
 
Ejemplos: 
 
 
*Main> first_two_minimals  (\a b -> fst a < fst b) [] 
[] 
*Main> first_two_minimals  (\a b -> fst a < fst b) [(5, 'a')] 
[(5,'a')] 
*Main> first_two_minimals  (\a b -> fst a < fst b) [(5, 'a'), (1, 'b')] 
[(1,'b')] 
*Main> first_two_minimals  (\a b -> fst a < fst b) [(5, 'a'), (1, 'b'), (2, 'c'), (4, 'd'), (1, 'e'), (3, 'f'), (1, 'g')] 
[(1,'b'),(1,'e')] 
*Main> 
 
-} 
 
-- Encuentra dos elementos menores que el resto, en orden y en la secuencia 
first_two_lowers :: (a -> a -> Bool) -> [a] -> [a] 
first_two_lowers isLessThan set = count $ first_two_minimals isLessThan set 
  where count []  = [] 
        count [x] = if null rs then [x] else x: [head rs] 
                    where rs = first_two_minimals isLessThan $ filter (x `isLessThan`) set 
        count xs  = xs 
 
 
{- 
 
Ejemplos: 
 
 
*Main> first_two_lowers  (\a b -> fst a < fst b) [] 
[] 
*Main> first_two_lowers  (\a b -> fst a < fst b) [(5, 'a')] 
[(5,'a')] 
*Main> first_two_lowers  (\a b -> fst a < fst b) [(5, 'a'), (1, 'b')] 
[(1,'b'),(5,'a')] 
*Main> first_two_lowers  (\a b -> fst a < fst b) [(5, 'a'), (1, 'b'), (2, 'c'), (4, 'd'), (1, 'e'), (3, 'f'), (1, 'g')] 
[(1,'b'),(1,'e')] 
*Main> 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.