2011-04-27 40 views
6

Por ejemplo, tengo la siguiente,en Haskell

type something = (Float, Float, Int, Aa, Bb, Cc, Int) 

Si tuviera que deseo encontrar la más pequeña something con base en su primer elemento (Float) ¿cómo podría hacerlo? La forma en que han razonado es la siguiente, sin embargo, no puedo lograr figureout cómo implementarlo

Porque tengo una lista de somethings la forma más fácil debería ser la creación de mi propia función min ayudante que compara 2 somethings y devuelve los más pequeños de los dos. Sin embargo, se trata de hacer que la "forma más fácil" que me quedé atrapado con tipo de errores de compilación ...

findMin :: something -> something -> somthing 
findMin x y = sortBy (compare `on` fst) x y 

no estoy familiarizado con sortBy y compare on, me encontré con una pregunta similar aquí en SO pero no pude lograr que funcione. Como un principiante en Haskell, ¿hay alguna otra manera de acercarte a esto?

+1

"fst" y "snd" solo funcionan en tuplas con dos elementos. Por algo más, probablemente estés mejor con "datos Algo = ..." como otros han sugerido. –

Respuesta

5

Usando una costumbre data tipo suele ser la mejor opción, pero si realmente desea utilizar tuplas, se puede empezar por definir una función de ayuda comparingFst que compara basa en el primer elemento de la tupla

import Data.Ord 
import Data.List 

-- Dummy data types for example purposes. Derive from Show just so 
-- that the example can be more easily tested interactively in ghci. 
data Aa = Aa deriving Show 
data Cc = Cc deriving Show 

type Something = (Float, Float, Int, Aa, Cc, Int) 

comparingFst :: Something -> Something -> Ordering 
comparingFst = comparing fstSomething 
    where fstSomething (x,_,_,_,_,_) = x 

Ahora usted puede tomar el menor de dos elementos con:

findMin :: Something -> Something -> Something 
findMin x y = case comparingFst x y of 
    LT -> x 
    _ -> y

o de una lista de elementos

findMinimum :: [Something] -> Something 
findMinimum = minimumBy comparingFst

Y también se puede utilizar la misma función auxiliar para la clasificación:

sortSomethings :: [Something] -> [Something] 
sortSomethings = sortBy comparingFst

Además, vale la pena mencionar que las tuplas se comparan por defecto con los elementos, comenzando por el primer elemento, por lo que suponiendo que los tipos Aa y Bb se pueden derivar de Ord y Eq, no necesita nada adicional, es decir, el ejemplo se convierte :

import Data.List 

data Ab = Ab deriving (Show, Ord, Eq) 
data Cc = Cc deriving (Show, Ord, Eq) 

type Something = (Float, Float, Int, Ab, Cc, Int) 

findMin :: Something -> Something -> Something 
findMin x y = min x y 

findMinimum :: [Something] -> Something 
findMinimum = minimum 

sortSomethings :: [Something] -> [Something] 
sortSomethings = sort

En otras palabras, sólo puede utilizar el estándar min y sort funciones tal y como son.

5

Tiene algunos errores de sintaxis, en primer lugar.

Hay dos cosas que puede hacer. En primer lugar, siguiendo el modelo de la utilización de una función de acceso para llegar al campo que desee (fst), podemos definir las etiquetas para los campos de su tipo:

data Something = Something { field_x, field_y :: Float, 
          field_z :: Int } 

y luego ordene field_x

import Data.List 
import Data.Function 

sortSomethings :: [Something] -> [Something] 
sortSomethings = sortBy (compare `on` field_x) 

conseguir en el mimimum es lo mismo que tomar la cabeza de la lista ordenada:

minSomethings :: [Something] -> Something 
minSomethings = head . sortSomethings 

alternativamente, se puede escribir una insta a medida Ord nce para el tipo Something que compara valores solo usando field_x, luego sort y minimum (y otras Ord-funciones basadas en regulares), "solo funcionará".

+0

Además, el 'que compara' es' compara en' –

6

Si desea comparar basándose en el primer campo de un tipo de datos, puede dejar que Haskell escribir el código para usted:

data Something = Something Float Float Int String Bool Char Int 
       deriving (Eq, Ord) 

La cláusula deriving especifica qué clases de tipos de implementaciones se generan automáticamente para el Something tipo. Aquí derivamos Eq que nos permite preguntar si dos Something s son iguales (por ejemplo, con ==) y Ord, lo que nos permite comparar dos Something y saber cuál es "mayor".

comportamiento predeterminado de Haskell al derivar Ord es comparar cada campo del primero al último, por lo que el código predeterminado se iniciará mediante la comparación de la primera Float de cada Something, que es exactamente lo que quiere.

Una vez que se trata de un tipo que implementa Ord, puede utilizar todo tipo de funciones integradas como minimum :: Ord a => [a] -> a. Esto toma una lista de cualquier tipo que implemente Ord y devuelve el elemento más pequeño.Así, como ejemplo:

st1 = Something 3.14 2.72 7 "hello" False 'λ' 42 
st2 = Something 3.15 2.72 7 "hello" False 'λ' 42 

smallest = minimum [st1,st2] 
+2

+1 para la simplicidad amigable para novatos –