higher - takewhile haskell

Mejorar mi implementación Haskell de filtro

Question

Recientemente me he enseñado a mí mismo Haskell, y uno de mis ejercicios fue volver a implementar la función de filter . Sin embargo, de todos los ejercicios que he realizado, mi respuesta para este me parece la más fea y larga. ¿Cómo podría mejorarlo? ¿Hay algún truco de Haskell que aún no sepa?

myfilter :: (a -> Bool) -> [a] -> [a]
myfilter f (x:xs) = if f x
then x : myfilter f xs
else myfilter f xs
myfilter _ [] = []

Gracias

Answer 1

¿Qué tal una lista de comprensión?

myfilter f xs = [x | x <- xs, f x]

Answer 2

A modo de comparación, aquí está la implementación de Wikipedia:

myfilter :: (a -> Bool) -> [a] -> [a]
myfilter _ [] = []
myfilter f (x:xs) | f x = x : myfilter f xs
| otherwise = myfilter f xs

Answer 3

Al menos, puede SECAR un poco sacando el código myfilter f xs común:

myfilter :: (a -> Bool) -> [a] -> [a]
myfilter f (x:xs) = if f x
then x : rest
else rest
where rest = myfilter f xs
myfilter _ [] = []

Answer 4

En Haskell, la mayoría de las veces puedes (y debes) usar guardias en lugar de si-entonces-otro:

myfilter :: (a -> Bool) -> [a] -> [a]
myfilter f (x:xs)
| f x = x : myfilter f xs
| otherwise = myfilter f xs
myfilter _ [] = []

Esto termina siendo básicamente la misma definición que se usa en la biblioteca estándar .

Answer 5

La forma más sencilla de mejorar tu implementación es usar guardias . En lugar de pattern = value , puede escribir pattern | boolean = value escritura pattern | boolean = value pattern | boolean = value ; esto solo coincidirá cuando boolean sea ​​verdadero. Por lo tanto, podemos obtener

filter1 :: (a -> Bool) -> [a] -> [a]
filter1 p (x:xs) | p x = x : filter1 p xs
| otherwise = filter1 p xs
filter1 _ [] = []

(Tenga en cuenta que, de lo otherwise es solo un sinónimo de True ). Ahora, tenemos filter p xs en dos lugares, por lo que podemos moverlo a una cláusula where ; estos son compartidos por todo lo que comparte un patrón común, incluso si tiene una guardia diferente:

filter2 :: (a -> Bool) -> [a] -> [a]
filter2 p (x:xs) | p x = x : xs''
| otherwise = xs''
where xs'' = filter2 p xs
filter2 _ [] = []

(Esta implementación es la utilizada por GHCs Prelude ).

Ahora, ninguno de estos son recursivos de la cola. Esto puede ser una desventaja, pero hace que la función sea floja. Si queremos una versión recursiva de cola, podríamos escribir

filter3 :: (a -> Bool) -> [a] -> [a]
filter3 p xs = let filter3'' p (x:xs) ys | p x = next $! x:ys
| otherwise = next $! ys
where next = filter3'' p xs
filter3'' _ [] ys = reverse ys
in filter3'' p xs []

Tenga en cuenta, sin embargo, que esto fallaría en listas infinitas (aunque todas las demás implementaciones funcionarán), gracias a la reverse , ¡así que lo hacemos estricto con $! . (Creo que lo hice bien, podría haber forzado la variable equivocada. Creo que esta fue la correcta).

Esas implementaciones parecen todas tuyas. Hay, por supuesto, otros. Uno está basado en foldr :

filter4 :: (a -> Bool) -> [a] -> [a]
filter4 p = let check x | p x = (x :)
| otherwise = id
in foldr check []

Aprovechamos el estilo sin puntos aquí; ya que xs sería el último argumento para filter4 y foldr check [] , podemos elide it, y de manera similar con el último argumento de check .

También puede aprovechar la lista de mónadas:

import Control.Monad
filter5 :: MonadPlus m => (a -> Bool) -> m a -> m a
filter5 p xs = do x <- xs
guard $ p x
return x

La lista de la mónada representa el no determinismo. Usted elige un elemento x de xs , asegúrese de que satisface p , y luego devuélvalo si lo hace. Todos estos resultados luego se recopilan juntos. Pero tenga en cuenta que esto ahora es más general; esto funciona para cualquier MonadPlus (una mónada que también es un monoide, es decir, que tiene una operación binaria asociativa mplus - ++ para listas - y un elemento de identidad mzero - [] para listas), como [] o Maybe . Por ejemplo, filter5 even $ Just 1 == Nothing , y filter5 even $ Just 2 == Just 2 .

También podemos adaptar la versión basada en foldr para obtener una firma de tipo genérico diferente:

import Control.Monad
import qualified Data.Foldable as F
import qualified Data.Monoid as M
filter6 :: (F.Foldable f, MonadPlus m, M.Monoid (m a))
=> (a -> Bool) -> f a -> m a
filter6 p = let check x | p x = return x
| otherwise = mzero
in F.foldMap check

El módulo Data.Foldable proporciona la clase de tipo Foldable , que representa cualquier estructura que se puede fold como una lista (colocando el resultado en un Monoid genérico). Nuestro filter requiere una restricción MonadPlus en el resultado para que podamos escribir return x . La función foldMap requiere una función que convierta todo en elementos de un Monoid , y luego los concatena a todos. La falta de coincidencia entre fa a la izquierda y ma a la derecha significa que podría, por ejemplo, filter6 a Maybe y obtener una lista.

Estoy seguro de que hay (¡muchas!) Otras implementaciones de filter , pero estas son las 6 que podría pensar con relativa rapidez. Ahora, ¿cuál de estos me gusta más? Es un lanzamiento entre el filter2 y el foldr basado en filter4 . Y filter5 es bueno para su firma de tipo genérico. (No creo que haya necesitado una firma de tipo como filter6 ''s). El hecho de que filter2 sea ​​usado por GHC es una ventaja, pero GHC también usa algunas reglas de reescritura funky, así que no es obvio para mí que es superior sin esos. Personalmente, probablemente iría con filter4 (o filter5 si necesitara la genericidad), pero filter2 está definitivamente bien.