Entendiendo el filtro de Haskell

Question

Entiendo que el filtro de Haskell es una función de orden alto (es decir, una función que toma otra función como parámetro) que pasa por una lista que verifica qué elemento cumple ciertas condiciones booleanas.

No acabo de entender su definición:

filter:: (a->Bool)->[a]->[a] 
filter p [] = [] 
filter p (x:y) | p x = x:filter p y 
       | otherwise = filter p y 

entiendo que si paso una lista vacía a la función, sólo se volvería una lista vacía, pero ¿cómo puedo leer las dos últimas líneas ?

Answer 1

Utiliza guards que si vienes de un lenguaje con una sintaxis de estilo C son un poco similares a la estructura switch.

El último patrón dice: Si la función p se evalúa como verdadera con el argumento x, devuelva el encabezado de la lista y la cola filtrada de la lista. De lo contrario, simplemente devuelva la cola filtrada de la lista.

También puede reescribir así:

filter p (x:y) = if ( p x) then 
        x:filter p y 
       else 
        filter p y 

Answer 2

Considere el description of filter in the docs:

filter, aplicado a un predicado y una lista, devuelve la lista de aquellos elementos que satisfacen el predicado; es decir,

filter p xs = [x | x <- xs, p x] 

explicarlo a alguien que no entiende las listas por comprensión, se podría decir filter tiene tres casos:

1. (El caso fácil) cuando la lista sea filtrado está vacío, el resultado también está vacío
2. cuando el encabezado de la lista a filtrar satisface el predicado, es parte del resultado
3. de lo contrario, omita la cabecera y filtre el resto de la lista

Estos casos corresponden uno a uno con las últimas tres líneas de la definición en su pregunta.

Los pequeños detalles pueden hacer que la definición más idiomática y por lo tanto más fácil de leer:

filter _ []  = [] 
filter p (x:xs) 
    | p x   = x : filter p xs 
    | otherwise =  filter p xs 

Para una lista vacía, el predicado puede ser nada en absoluto, y el subrayado indica explícitamente que no es importante en este caso.

En lugar de juego contra (x:y), utilizando (x:xs) -Piense: "ex y exes" -emphasizes que estás separar una lista en su cabeza (de tipo a) y la cola (de tipo [a], es decir, lista de a).

Por último, alinear las llamadas recursivas a filter permite fácilmente al lector ver que este último caso omite x.