Haskell – 25 – funzioni di ordine superiore – 2

Continuo da qui, copio qui, scrollare fino a “Filtering”.

The second recursive pattern on lists that we discussed in Recursion [posts precedenti] was filtering (which removes elements from a list). In particular, we discussed the two functions extractDigits, which extracts all digits from a string, and inRadius, which checks for points within a certain distance from another given point:

import Data.Char

extractDigits :: String -> String
extractDigits []
  = []
extractDigits (chr : restString)
  | isDigit chr = chr : extractDigits restString
  | otherwise   =       extractDigits restString

inRadius :: ColourPoint -> Float -> [ColourPoint] -> [ColourPoint]
inRadius point radius []
  = []
inRadius point radius (p : ps)
  | distance point p <= radius = p : inRadius point radius ps
  | otherwise                  =     inRadius point radius ps

Again, we can see that both functions have the same structure. The only meaningful difference between them is the test that decides whether we take the first recursive case (and keep the currently inspected list element) or whether we select the second recursive case (and drop the currently inspected element). The function inRadius gets additional arguments, but they are only passed down to the test that distinguishes the two functions. Tests (also called predicates) can be represented as functions from the tested value to a Boolean result; hence, it is natural to represent filtering as a higher-order function that takes a predicate as its function argument.

import Prelude hiding (filter)

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

It has the same structure as extractDigits and inRadius, but abstracts the test out as a predicate p. Hence, we can use filter to implement both extractDigits and inRadius:

extractDigits :: String -> String
extractDigits strings = filter isDigit strings

inRadius :: ColourPoint -> Float -> [ColourPoint] -> [ColourPoint]
inRadius point radius points = filter inRadiusP points
    inRadiusP :: ColourPoint -> Bool
    inRadiusP p = distance point p <= radius

Funzioni anonime
The definition of inRadius is an example where the use of a higher-order function gets somewhat verbose, as we need to define a local function (here, inRadiusP) to pass that function as an argument. The first occurrence of the same issue was the definition of allSquares. (In the case of distanceFromPoint, we also started out with a where clause, but we where able to eliminate that using partial application.)

We only use the local function inRadiusP once. Giving it a name and defining it separately from its use as an argument to filter seems cumbersome. To simplify cases like this, Haskell supports anonymous functions (sometimes called closures). These are function definitions without a name that can be defined inline; for example, as a function argument. Instead of a function equation of the form

functionName a1 a2 ... an = body

and then passing functionName as an argument, we simply write the expression

\a1 a2 ... an -> body

which represents the same n-ary function.

This enables us to shorten inRadius to

inRadius :: ColourPoint -> Float -> [ColourPoint] -> [ColourPoint]
inRadius point radius points = filter (\p -> distance point p <= radius) points

We read \p -> distance point p <= radius as “lambda p to distance point p <= radius” and also call it a lambda abstraction.

We can use the same technique with allSquares:

allSquares :: Num a => [a] -> [a]
allSquares xs = map (\x -> x * x) xs

Uhmmm… concetti già sentiti da altre parti (Lisp ma non solo). Certo che diventa tutto nuovo, da provare, raccolgo allSquares nel file allSq.hs:

*Main> :l allSq
[1 of 1] Compiling Main             ( allSq.hs, interpreted )
Ok, 1 module loaded.
*Main> allSquares [1, 2, 3, 4, 5]


Posta un commento o usa questo indirizzo per il trackback.



Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: