NAME

Language::Functional - a module which makes Perl slightly more functional

SYNOPSIS

use Language::Functional ':all';
print 'The first ten primes are: ', 
  show(take(10, filter { prime(shift) } 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.

$x = inc 2; # 3

In Haskell:

inc          :: a -> a
inc k         = 1 + k

double k

Doubles the passed value.

$x = double 3; # 6

In Haskell:

double         :: a -> a
double k        = k * 2

square k

Returns the square of the passed value. eg:

$x = square 3; # 9

In Haskell:

square          :: a -> a
square k         = k * k

gcd x y

Returns the greatest common denominator of two numbers. eg:

$x = 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:

$x = 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:

$x = 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:

$x = 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:

$x = Until { shift() % 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:

$x = 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:

$x = snd([1, 2]); # 2

In Haskell:

snd            :: (a,b) -> a
snd (_,y)       = y

head xs

Returns the head (first element) of a list. eg:

$x = 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:

$x = 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:

$x = 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:

$x = 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:

$x = 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:

$x = Map { double(shift) } [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:

$x = 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:

$x = 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:

$x = foldl { shift() + shift() } 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:

$x = foldl1 { shift() + shift() } [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:

$x = scanl { shift() + shift() }, 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:

$x = scanl1 { shift() + shift() } [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

$x = foldr { shift() + shift() } 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:

$x = foldr1 { shift() + shift() } [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:

$x = scanr { shift() + shift() } 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:

$x = scanr1 { shift() + shift() } [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:

$x = take(8, iterate { shift() * 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:

$x = 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:

$x = 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:

$x = 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:

$x = 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:

$x = 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:

$x = takeWhile { shift() <= 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:

$x = dropWhile { shift() <= 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:

$x = span { shift() <= 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:

$x = break { shift() >= 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:

$x = 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:

$x = 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:

$x = 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:

$x = 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:

$x = 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:

$x = 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:

$x = 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:

$x = any { even(shift) } [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:

$x = all { odd(shift) } [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:

$x = 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. eg:

$x = notElem(2, [1, 1, 3]); # 1

In Haskell:

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:

$x = 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

TODO: Make sure this works with infinite lists

minimum xs

Returns the minimum value in xs. You should not do this with a infinite list. eg:

$x = 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-2008, Leon Brocard

LICENSE

This module is free software; you can redistribute it or modify it under the same terms as Perl itself.