2010-04-02 24 views
5

Capisco che il filtro di Haskell è una funzione di ordine elevato (ovvero una funzione che prende un'altra funzione come parametro) che passa attraverso un elenco che controlla quale elemento soddisfa determinate condizioni booleane.Comprendere il filtro di Haskell

io non capisco la sua definizione:

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

ho capito che se mi passa una lista vuota alla funzione, sarebbe solo restituire un elenco vuoto, ma come faccio a leggere le ultime due righe ?

+0

@Justice: mi chiedo se il reformat è valido.Forse OP era davvero confuso dallo strano layout? – kennytm

risposta

11

utilizza guards che, se si proviene da una lingua con una sintassi stile C sono un po 'simile alla struttura switch.

L'ultimo modello indica: Se la funzione p restituisce true con l'argomento x, restituire il capo dell'elenco e la coda filtrata dell'elenco. Altrimenti, basta restituire la coda filtrata della lista.

Si potrebbe anche riscrivere in questo modo:

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

Anche 'altrimenti' è definito come' Vero' nel preludio. –

7

consideri il description of filter in the docs:

filter, applicato ad un predicato e una lista, restituisce la lista di quegli elementi che soddisfano il predicato; cioè,

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

di spiegarlo a qualcuno che non capisce list comprehension, si potrebbe dire filter ha tre casi:

  1. (il caso facile) quando la lista per essere filtrato è vuota, il risultato è vuoto
  2. quando la testa della lista da filtrare soddisfa il predicato, è parte del risultato
  3. altrimenti, salta la testa e filtra il resto della lista

Questi casi corrispondono uno a uno con le ultime tre righe della definizione nella tua domanda.

Piccoli tocchi possono rendere la definizione più idiomatica e quindi più facile da leggere:

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

Per un elenco vuoto, il predicato può essere qualsiasi cosa a tutti, e la sottolineatura indica esplicitamente che è poco importante in questo caso.

Piuttosto che la corrispondenza con (x:y), utilizzando (x:xs) -Pensate: "ex e exes" -emphasizes che si sta separando una lista nella sua testa (di tipo a) e la coda (di tipo [a], cioè, elenco delle a).

Infine, allineando le chiamate ricorsive a filter permette facilmente al lettore di vedere che quest'ultimo caso omette x.

Problemi correlati