NAME
Functional - a module which makes Perl slightly more functional
(think Haskell)
SYNOPSIS
use Functional;
print 'The first ten primes are: ',
show(take(10, filter("prime", integers))), "\n";
DESCRIPTION
Perl already contains some functional-like functions, such as
`map' and `grep'. The purpose of this module is to add other
functional-like functions to Perl, such as foldl and foldr, as
well as the use of infinite lists.
Think as to how you would express the first ten prime numbers in
a simple way in your favourite programming language? So the
example in the synopsis is a killer app, if you will (until I
think up a better one ;-).
The idea is mostly based on Haskell, from which most of the
functions are taken. There are a couple of major omissions:
currying and types. Lists (and tuples) are simply Perl list
references, none of this 'cons' business, and strings are simple
strings, not lists of characters.
The idea is to make Perl slightly more functional, rather than
completely replace it. Hence, this slots in very well with
whatever else your program may be doing, and is very Perl-ish.
Other modules are expected to try a much more functional
approach.
FUNCTIONS
The following functions are available. (Note: these should not
be called as methods).
In each description, I shall give the Haskell definition (if I
think it would help) as well as a useful example.
show
Show returns a string representation of an object. It does
not like infinite lists.
inc k
Increases the value passed by 1. eg: inc(2) = 3. In Haskell:
inc :: a -> a
inc k = 1 + k
double k
Doubles the passed value. eg: double(3) = 6. In Haskell:
double :: a -> a
double k = k * 2
square k
Returns the square of the passed value. eg: square(3) = 9.
In Haskell:
square :: a -> a
square k = 1 + k
gcd x y
Returns the greatest common denominator of two numbers. eg:
gcd(144, 1024) = 16. In Haskell:
gcd :: Integral a => a -> a -> a
gcd 0 0 = error "gcd 0 0 is undefined"
gcd x y = gcd' (abs x) (abs y)
where gcd' x 0 = x
gcd' x y = gcd' y (x `rem` y)
lcm x y
Returns the lowest common multiple of two numbers. eg:
lcm(144, 1024) = 9216. In Haskell:
lcm :: (Integral a) => a -> a -> a
lcm _ 0 = 0
lcm 0 _ = 0
lcm x y = abs ((x `quot` gcd x y) * y)
id x
The identity function - simply returns the argument. eg:
id([1..6]) = [1, 2, 3, 4, 5, 6]. In Haskell:
id :: a -> a
id x = x
const k _
Returns the first argument of 2 arguments. eg: const(4, 5) =
4. In Haskell:
const :: a -> b -> a
const k _ = k
flip f
Given a function, flips the two arguments it is passed. Note
that this returns a CODEREF, as currying does not yet
happen. eg: flip(sub { $_[0] ** $_[1] })->(2, 3) = 9. In
Haskell (ie this is what it should really do):
flip :: (a -> b -> c) -> b -> a -> c
flip f x y = f y x
Until p f x
Keep on applying f to x until p(x) is true, and then return
x at that point. eg: Until(sub { $_[0] % 10 == 0 }, "inc",
1) = 10. In Haskell:
until :: (a -> Bool) -> (a -> a) -> a -> a
until p f x = if p x then x else until p f (f x)
fst x:xs
Returns the first element in a tuple. eg: fst([1, 2]) = 1.
In Haskell:
fst :: (a,b) -> a
fst (x,_) = x
snd x:y:xs
Returns the second element in a tuple. eg: snd([1, 2]) = 2.
In Haskell:
snd :: (a,b) -> a
snd (_,y) = y
head xs
Returns the head (first element) of a list. eg: head([1..6])
= 1. In Haskell:
head :: [a] -> a
head (x:_) = x
Last xs
Returns the last element of a list. Note the capital L, to
make it distinct from the Perl 'last' command. eg:
Last([1..6]) = 6. In Haskell:
last :: [a] -> a
last [x] = x
last (_:xs) = last xs
tail xs
Returns a list minus the first element (head). eg:
tail([1..6]) = [2, 3, 4, 5, 6]. In Haskell:
tail :: [a] -> [a]
tail (_:xs) = xs
init xs
Returns a list minus its last element. eg: init([1..6]) =
[1, 2, 3, 4, 5]. In Haskell:
init :: [a] -> [a]
init [x] = []
init (x:xs) = x : init xs
null xs
Returns whether or not the list is empty. eg: null([1, 2]) =
False. In Haskell:
null :: [a] -> Bool
null [] = True
null (_:_) = False
Map f xs
Evaluates f for each element of the list xs and returns the
list composed of the results of each such evaluation. It is
very similar to the Perl command 'map', hence the capital M,
but also copes with infinite lists. eg: Map("double",
[1..6]) = [2, 4, 6, 8, 10, 12]. In Haskell:
map :: (a -> b) -> [a] -> [b]
map f xs = [ f x | x <- xs ]
filter p xs
Returns the list of the elements in xs for which p(xs)
returns true. It is similar to the Perl command 'grep', but
it also copes with infinite lists. eg: filter("even",
[1..6]) = [2, 4, 6]. In Haskell:
filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [ x | x <- xs, p x ]
concat
Concatenates lists together into one list. eg:
concat([[1..3], [4..6]]) = [1, 2, 3, 4, 5, 6]. In Haskell:
concat :: [[a]] -> [a]
concat = foldr (++) []
TODO: Make sure this works with infinite lists!
Length
Returns the length of a list - only do this with finite
lists! eg: Length([1..6]) = 6. In Haskell:
length :: [a] -> Int length = foldl' (\n _ -> n + 1) 0
TODO Make sure this works!
foldl f z xs
Applies function f to the pairs (z, xs[0]), (f(z, xs[0],
xs[1]), (f(f(z, xs[0], xs[1])), xs[2]) and so on. ie it
folds from the left and returns the last value. Note that
foldl should not be done to infinite lists. eg: the
following returns the sum of 1..6: foldl(sub { $_[0] + $_[1]
}, 0, [1..6]) = 21. In Haskell:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
foldl1 f xs
This is a variant of foldl where the first value of xs is
taken as z. Applies function f to the pairs (xs[0], xs[1]),
(f(xs[0], xs[1], xs[2]), (f(f(xs[0], xs[1], xs[2])), xs[3])
and so on. ie it folds from the left and returns the last
value. Note that foldl should not be done to infinite lists.
eg: the following returns the sum of 1..6: foldl1(sub {
$_[0] + $_[1] }, [1..6]) = 21. In Haskell:
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
scanl f q xs
Returns a list of all the intermedia values that foldl would
compute. ie returns the list z, f(z, xs[0]), f(f(z, xs[0]),
xs[1]), f(f(f(z, xs[0]), xs[1]), xs[2]) and so on. eg:
scanl(sub { $_[0] + $_[1] }, 0, [1..6]) = [0, 1, 3, 6, 10,
15, 21]. In Haskell:
scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanl f q xs = q : (case xs of
[] -> []
x:xs -> scanl f (f q x) xs)
scanl1 f xs
This is a variant of scanl where the first value of xs is
taken as q. Returns a list of all the intermedia values that
foldl would compute. ie returns the list f(xs[0], xs[1]),
f(f(xs[0], xs[1]), xs[2]), f(f(f(xs[0], xs[1]), xs[2]),
xs[3]) and so on. eg: scanl1(sub { $_[0] + $_[1] }, [1..6])
= [1, 3, 6, 10, 15, 21]. In Haskell:
scanl1 :: (a -> a -> a) -> [a] -> [a]
scanl1 f (x:xs) = scanl f x xs
foldr f z xs
This is similar to foldl but is folding from the right
instead of the left. Note that foldr should not be done to
infinite lists. eg: the following returns the sum of 1..6:
foldl(sub { $_[0] + $_[1] }, 0, [1..6]) = 21. In Haskell:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
foldr1 f xs
This is similar to foldr1 but is folding from the right
instead of the left. Note that foldr1 should not be done on
infinite lists. eg: foldr1(sub { $_[0] + $_[1] }, [1..6]) =
21. In Haskell:
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 f [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)
scanr f z xs
This is similar to scanl but is scanning and folding from
the right instead of the left. Note that scanr should not be
done on infinite lists. eg: scanr(sub { $_[0] + $_[1] }, 0,
[1..6]) = [0, 6, 11, 15, 18, 20, 21]. In Haskell:
scanr :: (a -> b -> b) -> b -> [a] -> [b]
scanr f q0 [] = [q0]
scanr f q0 (x:xs) = f x q : qs
where qs@(q:_) = scanr f q0 xs
scanr1 f xs
This is similar to scanl1 but is scanning and folding from
the right instead of the left. Note that scanr1 should not
be done on infinite lists. eg: scanr1(sub { $_[0] + $_[1] },
[1..6]) = [6, 11, 15, 18, 20, 21]. In Haskell:
scanr1 :: (a -> a -> a) -> [a] -> [a]
scanr1 f [x] = [x]
scanr1 f (x:xs) = f x q : qs
where qs@(q:_) = scanr1 f xs
iterate f x
This returns the infinite list (x, f(x), f(f(x)),
f(f(f(x)))...) and so on. eg: take(8, iterate(sub { $_[0]*2
}, 1)) = [1, 2, 4, 8, 16, 32, 64, 128]. In Haskell:
iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)
repeat x
This returns the infinite list where all elements are x. eg:
take(4, repeat(42)) = [42, 42, 42, 42]. In Haskell:
repeat :: a -> [a]
repeat x = xs where xs = x:xs
replicate n x
Returns a list containing n times the element x. eg:
replicate(5, 1) = [1, 1, 1, 1, 1]. In Haskell:
replicate :: Int -> a -> [a]
replicate n x = take n (repeat x)
take n xs
Returns a list containing the first n elements from the list
xs. eg: take(2, [1..6]) = [1, 2]. In Haskell:
take :: Int -> [a] -> [a]
take 0 _ = []
take _ [] = []
take n (x:xs) | n>0 = x : take (n-1) xs
take _ _ = error "Prelude.take: negative argument"
drop n xs
Returns a list containing xs with the first n elements
missing. eg: drop(2, [1..6]) = [3, 4, 5, 6]. In Haskell:
drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
drop n (_:xs) | n>0 = drop (n-1) xs
drop _ _ = error "Prelude.drop: negative argument"
splitAt n xs
Splits the list xs into two lists at element n. eg:
splitAt(2, [1..6]) = [[1, 2], [3, 4, 5, 6]]. In Haskell:
splitAt :: Int -> [a] -> ([a], [a])
splitAt 0 xs = ([],xs)
splitAt _ [] = ([],[])
splitAt n (x:xs) | n>0 = (x:xs',xs'') where (xs',xs'') = splitAt (n-1) xs
splitAt _ _ = error "Prelude.splitAt: negative argument"
takeWhile p xs
Takes elements from xs while p(that element) is true.
Returns the list. eg: takeWhile(sub { $_[0] <= 4 }, [1..6])
= [1, 2, 3, 4]. In Haskell:
takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile p [] = []
takeWhile p (x:xs)
| p x = x : takeWhile p xs
| otherwise = []
dropWhile p xs
Drops elements from the head of xs while p(that element) is
true. Returns the list. eg: dropWhile(sub { $_[0] <= 4 },
[1..6]) = [5, 6]. In Haskell:
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile p [] = []
dropWhile p xs@(x:xs')
| p x = dropWhile p xs'
| otherwise = xs
span p xs
Splits xs into two lists, the first containing the first few
elements for which p(that element) is true. eg: span(sub {
$_[0] <= 4 }, [1..6]) = [[1, 2, 3, 4], [5, 6]]. In Haskell:
span :: (a -> Bool) -> [a] -> ([a],[a])
span p [] = ([],[])
span p xs@(x:xs')
| p x = (x:ys, zs)
| otherwise = ([],xs)
where (ys,zs) = span p xs'
break p xs
Splits xs into two lists, the first containing the first few
elements for which p(that element) is false. eg: break(sub {
$_[0] >= 4 }, [1..6]) = [[1, 2, 3], [4, 5, 6]]. In Haskell:
break :: (a -> Bool) -> [a] -> ([a],[a])
break p = span (not . p)
lines s
Breaks the string s into multiple strings, split at line
boundaries. eg: lines("A\nB\nC") = ['A', 'B', 'C']. In
Haskell:
lines :: String -> [String]
lines "" = []
lines s = let (l,s') = break ('\n'==) s
in l : case s' of [] -> []
(_:s'') -> lines s''
words s
Breaks the string s into multiple strings, split at
whitespace boundaries. eg: words("hey how random") = ['hey',
'how', 'random']. In Haskell:
words :: String -> [String]
words s = case dropWhile isSpace s of
"" -> []
s' -> w : words s''
where (w,s'') = break isSpace s'
unlines xs
Does the opposite of unlines, that is: joins multiple
strings into one, joined by newlines. eg: unlines(['A', 'B',
'C']) = "A\nB\nC"; In Haskell:
unlines :: [String] -> String
unlines = concatMap (\l -> l ++ "\n")
(note that strings in Perl are not lists of characters, so
this approach will not actually work...)
unwords ws
Does the opposite of unwords, that is: joins multiple
strings into one, joined by a space. eg:
unwords(["hey","how","random"]) = 'hey how random'. In
Haskell:
unwords :: [String] -> String
unwords [] = []
unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
Reverse xs
Returns a list containing the elements of xs in reverse
order. Note the capital R, so as not to clash with the Perl
command 'reverse'. You should not try to Reverse an infinite
list. eg: Reverse([1..6]) = [6, 5, 4, 3, 2, 1]. In Haskell:
reverse :: [a] -> [a]
reverse = foldl (flip (:)) []
And xs
Returns true if all the elements in xs are true. Returns
false otherwise. Note the capital A, so as not to clash with
the Perl command 'and'. You should not try to And an
infinite list (unless you expect it to fail, as it will
short-circuit). eg: And([1, 1, 1]) = 1. In Haskell:
and :: [Bool] -> Bool
and = foldr (&&) True
Or xs
Returns true if one of the elements in xs is true. Returns
false otherwise. Note the capital O, so as not to clash with
the Perl command 'or'. You may try to Or an infinite list as
it will short-circuit (unless you expect it to fail, that
is). eg: Or([0, 0, 1]) = 1. In Haskell:
or :: [Bool] -> Bool
or = foldr (||) False
any p xs
Returns true if one of p(each element of xs) are true.
Returns false otherwise. You should not try to And an
infinite list (unless you expect it to fail, as it will
short-circuit). eg: any("even", [1, 2, 3]) = 1. In Haskell:
any :: (a -> Bool) -> [a] -> Bool
any p = or . map p
all p xs
Returns true if all of the p(each element of xs) is true.
Returns false otherwise. You may try to Or an infinite list
as it will short-circuit (unless you expect it to fail, that
is). eg: all("odd", [1, 1, 3]) = 1. In Haskell:
all :: (a -> Bool) -> [a] -> Bool
all p = and . map p
elem x xs
Returns true is x is present in xs. You probably should not
do this with infinite lists. Note that this assumes x and xs
are numbers. eg: elem(2, [1, 2, 3]) = 1. In Haskell:
elem :: Eq a => a -> [a] -> Bool
elem = any . (==)
notElem x xs
Returns true if x is not present in x. You should not do
this with infinite lists. Note that this assumes that x and
xs are numbers.
notElem :: Eq a => a -> [a] -> Bool
notElem = all . (/=)
lookup key xys
This returns the value of the key in xys, where xys is a
list of key, value pairs. It returns undef if the key was
not found. You should not do this with infinite lists. Note
that this assumes that the keys are strings. eg: lookup(3,
[1..6]) = 4. In Haskell:
lookup :: Eq a => a -> [(a,b)] -> Maybe b
lookup k [] = Nothing
lookup k ((x,y):xys)
| k==x = Just y
| otherwise = lookup k xys
minimum xs
Returns the minimum value in xs. You should not do this with
a infinite list. eg: minimum([1..6]) = 1. In Haskell:
minimum :: Ord a => [a] -> a
minimum = foldl1 min
maximum xs
Returns the maximum value in xs. You should not do this with
an infinite list. eg: maximum([1..6]) = 6. In Haskell:
maximum :: Ord a => [a] -> a
maximum = foldl1 max
sum xs
Returns the sum of the elements of xs. You should not do
this with an infinite list. eg: sum([1..6]) = 21. In
Haskell:
sum :: Num a => [a] -> a
sum = foldl' (+) 0
product xs
Returns the products of the elements of xs. You should not
do this with an infinite list. eg: product([1..6]) = 720. In
Haskell:
product :: Num a => [a] -> a
product = foldl' (*) 1
zip as bs
Zips together two lists into one list. Should not be done
with infinite lists. eg: zip([1..6], [7..12]) = [1, 7, 2, 8,
3, 9, 4, 10, 5, 11, 6, 12]. In Haskell:
zip :: [a] -> [b] -> [(a,b)]
zip = zipWith (\a b -> (a,b))
zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith z (a:as) (b:bs) = z a b : zipWith z as bs
zipWith _ _ _ = []
zip3 as bs cs
Zips together three lists into one. Should not be done with
infinite lists. eg: zip3([1..2], [3..4], [5..6]) = [1, 3, 5,
2, 4, 6]. In Haskell:
zip3 :: [a] -> [b] -> [c] -> [(a,b,c)]
zip3 = zipWith3 (\a b c -> (a,b,c))
zipWith3 :: (a->b->c->d) -> [a]->[b]->[c]->[d]
zipWith3 z (a:as) (b:bs) (c:cs)
= z a b c : zipWith3 z as bs cs
zipWith3 _ _ _ _ = []
unzip abs
Unzips one list into two. Should not be done with infinite
lists. eg: unzip([1,7,2,8,3,9,4,10,5,11,6,12]) = ([1, 2, 3,
4, 5, 6], [7, 8, 9, 10, 11, 12]).
unzip :: [(a,b)] -> ([a],[b])
unzip = foldr (\(a,b) ~(as,bs) -> (a:as, b:bs)) ([], [])
unzip abcs
Unzips one list into three. Should not be done with infinite
lists. eg: unzip3([1,3,5,2,4,6]) = ([1, 2], [3, 4], [5, 6]).
In Haskell:
unzip3 :: [(a,b,c)] -> ([a],[b],[c])
unzip3 = foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
([],[],[])
integers
A useful function that returns an infinite list containing
all the integers. eg: integers = (1, 2, 3, 4, 5, ...).
factors x
A useful function that returns the factors of x. eg:
factors(100) = [1, 2, 4, 5, 10, 20, 25, 50, 100]. In
Haskell:
factors x = [n | n <- [1..x], x `mod` n == 0]
prime x
A useful function that returns, rather unefficiently, if x
is a prime number or not. It is rather useful while used as
a filter, eg: take(10, filter("prime", integers)) = [2, 3,
5, 7, 11, 13, 17, 19, 23, 29]. In Haskell:
primes = [n | n <- [2..], length (factors n) == 2]
AUTHOR
Leon Brocard <acme@astray.com>
COPYRIGHT
Copyright (C) 1999, Leon Brocard
This module is free software; you can redistribute it or modify
it under the same terms as Perl itself.