Programming « Rod Carvalho

Archive for the ‘Programming’ Category

Perfect shuffles in Haskell

April 17, 2012

Consider a deck of $2 n$ cards. There exists a bijection from the set of cards to the finite set $\{1, 2, \dots, 2 n\}$ , which allows us to represent the deck using a ( $2 n$ )-tuple, as follows

$(1, 2, \dots, n, n+1, n+2, \dots, 2 n)$

where the first element represents the card at the top of the deck, and the ( $2 n$ )-th element represents the card at the bottom of the deck. A perfect shuffle consists of cutting the deck exactly in half and then interlacing / interleaving the two halves perfectly. The in shuffle moves the original top card to the second position. The out shuffle leaves the original top card on top [1]. After a perfect in shuffle the deck will be

$(n+1, 1, n+2, 2, \dots, 2 n, n)$ ,

whereas after a perfect out shuffle the deck will be

$(1, n+1, 2, n+2, \dots, n, 2 n)$ .

Is it possible to restore the deck to its original order after a certain number of perfect shuffles? Amazingly (or perhaps not), it is indeed possible!

__________

Example 1

Suppose we are given a deck of $8$ cards (i.e., $n = 4$ ). A perfect out shuffle of this deck is depicted below

[ source ]

Using pencil and paper, it is easy to see that after three perfect out shuffles the deck will be restored to its original order. Here is a Haskell script:

-- create Card data type
data Card = Ace | Two | Three | Four | 
            Five | Six | Seven | Eight 
            deriving (Show, Eq)

-- create type synonym
type Deck = [Card]

-- interlace two decks of the same size
interlace :: Deck -> Deck -> Deck
interlace [] [] = []
interlace (c1:d1) (c2:d2) = [c1,c2] ++ interlace d1 d2

-- perfect out shuffle
outShuffle :: Deck -> Deck
outShuffle deck = interlace deck1 deck2
                  where deck1 = fst (splitAt 4 deck)
                        deck2 = snd (splitAt 4 deck)

-- perfect in shuffle
inShuffle :: Deck -> Deck
inShuffle deck = interlace deck2 deck1
                 where deck1 = fst (splitAt 4 deck)
                       deck2 = snd (splitAt 4 deck)

where I used function splitAt to cut the deck into two halves of equal size. Since I am not acquainted with any function that performs interleaving, I did create my own function. We load this script into GHCi. Here is a brief GHCi session:

*Main> -- create deck
*Main> let deck = [Ace,Two,Three,Four,Five,Six,Seven,Eight]
*Main> -- perform 3 out shuffles
*Main> take 4 (iterate outShuffle deck)
[[Ace,Two,Three,Four,Five,Six,Seven,Eight],
 [Ace,Five,Two,Six,Three,Seven,Four,Eight],
 [Ace,Three,Five,Seven,Two,Four,Six,Eight],
 [Ace,Two,Three,Four,Five,Six,Seven,Eight]]
*Main>

Indeed, after three perfect out shuffles, we do obtain a deck in the original order! One is tempted to wonder what the order of the deck will be after three perfect in shuffles. Let us see:

*Main> -- create deck
*Main> let deck = [Ace,Two,Three,Four,Five,Six,Seven,Eight]
*Main> -- perform 3 in shuffles
*Main> take 4 (iterate inShuffle deck)
[[Ace,Two,Three,Four,Five,Six,Seven,Eight],
 [Five,Ace,Six,Two,Seven,Three,Eight,Four],
 [Seven,Five,Three,Ace,Eight,Six,Four,Two],
 [Eight,Seven,Six,Five,Four,Three,Two,Ace]]

After three perfect in shuffles we do not obtain the original deck. Instead, we obtain a reversal of the original deck.

__________

Example 2

Let us now work with the standard deck of $52$ cards. People say that eight consecutive perfect out shuffles will restore the deck to its original order. Let us check whether this is true or not.

Here is a new Haskell script:

-- create Value data type
data Value = Ace | Two | Three | Four | Five | Six | Seven | Eight | 
             Nine | Ten | Jack | Queen | King deriving (Show, Eq)

-- create Suit data type
data Suit  = Club | Diamond | Heart | Spade deriving (Show, Eq)

-- create type synonyms
type Card = (Value,Suit)
type Deck = [Card]

-- create list of card values
values :: [Value]
values = [Ace,Two,Three,Four,Five,Six,Seven,
          Eight,Nine,Ten,Jack,Queen,King]

-- create list of card suits
suits :: [Suit]
suits = [Club,Diamond,Heart,Spade]

-- create deck
deck :: Deck
deck = [(v,s) | v <- values, s <- suits] 

-- interlace two decks of the same size
interlace :: Deck -> Deck -> Deck
interlace [] [] = []
interlace (c1:d1) (c2:d2) = [c1,c2] ++ interlace d1 d2

-- perfect out shuffle
outShuffle :: Deck -> Deck
outShuffle deck = interlace deck1 deck2
                  where n = div (length deck) 2
                        deck1 = fst (splitAt n deck)
                        deck2 = snd (splitAt n deck)

-- perfect in shuffle
inShuffle :: Deck -> Deck
inShuffle deck = interlace deck2 deck1
                 where n = div (length deck) 2
                       deck1 = fst (splitAt n deck)
                       deck2 = snd (splitAt n deck)

We load this script into GHCi. Here is a GHCi session:

*Main> -- print deck
*Main> deck
[(Ace,Club),(Ace,Diamond),(Ace,Heart),(Ace,Spade),
 (Two,Club),(Two,Diamond),(Two,Heart),(Two,Spade),
 (Three,Club),(Three,Diamond),(Three,Heart),(Three,Spade),
 (Four,Club),(Four,Diamond),(Four,Heart),(Four,Spade),
 (Five,Club),(Five,Diamond),(Five,Heart),(Five,Spade),
 (Six,Club),(Six,Diamond),(Six,Heart),(Six,Spade),
 (Seven,Club),(Seven,Diamond),(Seven,Heart),(Seven,Spade),
 (Eight,Club),(Eight,Diamond),(Eight,Heart),(Eight,Spade),
 (Nine,Club),(Nine,Diamond),(Nine,Heart),(Nine,Spade),
 (Ten,Club),(Ten,Diamond),(Ten,Heart),(Ten,Spade),
 (Jack,Club),(Jack,Diamond),(Jack,Heart),(Jack,Spade),
 (Queen,Club),(Queen,Diamond),(Queen,Heart),(Queen,Spade),
 (King,Club),(King,Diamond),(King,Heart),(King,Spade)]
*Main> -- perform 8 out shuffles
*Main> let deck8 = (iterate outShuffle deck) !! 8
*Main> -- is the new deck the same as the original one?
*Main> deck8 == deck
True

Indeed, it is true! Eight perfect out shuffles suffice!

__________

References

[1] Persi Diaconis, R. L. Graham, William M. Kantor, The Mathematics of Perfect Shuffles, Advances in Applied Mathematics, Volume 4, Issue 2, June 1983.

Tags:Card Shuffling, Card Tricks, Haskell, List Processing, Perfect Shuffle
Posted in Haskell | 4 Comments »

Digraphs in Haskell

April 3, 2012

A directed graph (or digraph) is an ordered pair $D = (V, A)$ , where $V$ is a non-empty finite set of elements called vertices, and $A$ is a finite set of elements called arcs, where an arc is an ordered pair of distinct vertices [1]. We call $V$ and $A$ the vertex set and the arc set, respectively. Note that $A \subseteq V \times V$ . For an arc $(v_i, v_j)$ , we call $v_i$ the tail, and $v_j$ the head, and say that the arc $(v_i, v_j)$ leaves vertex $v_i$ and enters vertex $v_j$ .

For instance, consider the digraph depicted below

This digraph has 10 vertices and 15 arcs. How would we build this digraph in Haskell? A vertex could be represented by an integer, and an arc could be represented by an ordered pair of integers. However, in Mathematics we work with sets, whereas in Haskell we work with lists. Hence, we could represent the vertex set by a list of vertices, and the arc set by a list of edges.

Here is a simplistic implementation:

-- type synonyms
type Vertex  = Int
type Arc     = (Vertex,Vertex)
type Digraph = ([Vertex],[Arc])

-- create list of vertices
vs :: [Vertex]
vs = [1..10]

-- create list of arcs
as :: [Arc]
as = [(1,4),(1,5),(1,6),(2,4),(3,4),
      (4,5),(5,6),(7,6),(8,1),(8,2),
      (8,7),(9,8),(9,10),(10,2),(10,3)]

-- create digraph
digraph :: Digraph
digraph = (vs,as)

We load this script in GHCi and perform some simple testing:

*Main> -- list of vertices
*Main> vs
[1,2,3,4,5,6,7,8,9,10]
*Main> length vs
10
*Main> -- list of arcs
*Main> as
[(1,4),(1,5),(1,6),(2,4),(3,4),(4,5),(5,6),(7,6),
(8,1),(8,2),(8,7),(9,8),(9,10),(10,2),(10,3)]
*Main> length as
15
*Main> -- digraph
*Main> digraph
([1,2,3,4,5,6,7,8,9,10],[(1,4),(1,5),(1,6),
(2,4),(3,4),(4,5),(5,6),(7,6),(8,1),(8,2),
(8,7),(9,8),(9,10),(10,2),(10,3)])

We have thus created a digraph. What can we do with it? Is there anything of interest that we could compute?

__________

Neighborhoods

Given a digraph $D = (V, A)$ , we call the following sets

$N_D^{+} (v) = \{ u \in V \mid (v, u) \in A\}$

$N_D^{-} (v) = \{ u \in V \mid (u, v) \in A\}$

the out-neighborhood of vertex $v$ and the in-neighborhood of vertex $v$ , respectively [1]. The vertices in $N_D^{+} (v)$ and $N_D^{-} (v)$ are called the out-neighbors and the in-neighbors of vertex $v$ , respectively.

In Haskell, we compute the out- and in-neighborhoods as follows:

-- compute out-neighborbood of a vertex
outNeighbors :: Digraph -> Vertex -> [Vertex]
outNeighbors (vs,as) v = map snd (filter (p v) as)
                         where p v (t,h) | t == v = True
                                         | t /= v = False

-- compute in-neighborbood of a vertex
inNeighbors :: Digraph -> Vertex -> [Vertex]
inNeighbors (vs,as) v = map fst (filter (p v) as)
                        where p v (t,h) | h == v = True
                                        | h /= v = False

Let us do some testing in GHCi:

*Main> -- list of all out-neighborhoods
*Main> map (outNeighbors digraph) vs
[[4,5,6],[4],[4],[5],[6],[],[6],[1,2,7],[8,10],[2,3]]
*Main> -- list of all in-neighborhoods
*Main> map (inNeighbors digraph) vs
[[8],[8,10],[10],[1,2,3],[1,4],[1,5,7],[8],[9],[],[9]]

__________

Degrees

Given a digraph $D = (V, A)$ , we call the following cardinalities

$d_D^{+} (v) = |N_D^{+} (v)|$

$d_D^{-} (v) = |N_D^{-} (v)|$

the out-degree and the in-degree of vertex $v$ , respectively [1]. We compute the out- and in-degrees in Haskell as follows:

-- compute out-degree of a vertex
outDegree :: Digraph -> Vertex -> Int
outDegree (vs,as) v = length (outNeighbors (vs,as) v)

-- compute in-degree of a vertex
inDegree :: Digraph -> Vertex -> Int
inDegree (vs,as) v = length (inNeighbors (vs,as) v)

Let us do some testing in GHCi:

*Main> -- out-degrees of all vertices
*Main> map (outDegree digraph) vs
[3,1,1,1,1,0,1,3,2,2]
*Main> -- in-degrees of all vertices
*Main> map (inDegree digraph) vs
[1,2,1,3,2,3,1,1,0,1]

__________

Concluding remarks

Here is the whole Haskell script:

-- type synonyms
type Vertex  = Int
type Arc     = (Vertex,Vertex)
type Digraph = ([Vertex],[Arc])

-- create list of vertices
vs :: [Vertex]
vs = [1..10]

-- create list of arcs
as :: [Arc]
as = [(1,4),(1,5),(1,6),(2,4),(3,4),
      (4,5),(5,6),(7,6),(8,1),(8,2),
      (8,7),(9,8),(9,10),(10,2),(10,3)]

-- create digraph
digraph :: Digraph
digraph = (vs,as)

-- compute out-neighborbood of a vertex
outNeighbors :: Digraph -> Vertex -> [Vertex]
outNeighbors (vs,as) v = map snd (filter (p v) as)
                         where p v (t,h) | t == v = True
                                         | t /= v = False

-- compute in-neighborbood of a vertex
inNeighbors :: Digraph -> Vertex -> [Vertex]
inNeighbors (vs,as) v = map fst (filter (p v) as)
                        where p v (t,h) | h == v = True
                                        | h /= v = False

-- compute out-degree of a vertex
outDegree :: Digraph -> Vertex -> Int
outDegree (vs,as) v = length (outNeighbors (vs,as) v)

-- compute in-degree of a vertex
inDegree :: Digraph -> Vertex -> Int
inDegree (vs,as) v = length (inNeighbors (vs,as) v)

We now know how to create digraphs in Haskell and compute simple things, like neighborhoods and degrees. What else would it be of interest to compute?

__________

References

[1] Jørgen Bang-Jensen, Gregory Z. Gutin, Digraphs: Theory, Algorithms and Applications (2nd edition), Springer, 2009.

Tags:Digraphs, Directed Graphs, Graph Theory, Haskell
Posted in Graph Theory, Haskell | Leave a Comment »

Newton’s method using rational arithmetic

April 2, 2012

The floating-point number system puts further restraints on what can be expected. We can at best hope to keep the relative error under control, and we cannot expect to find zeros far from the origin with great absolute accuracy.

– Richard W. Hamming [1]

I am somewhat disenchanted with floating-point arithmetic. We all have implemented numerical methods using floating-point numbers. But, how many of us have implemented numerical methods using rational numbers of arbitrary precision? I certainly have not. Hence, let us give it a try. In this post I will implement Newton’s method [1] (also known as the Newton-Raphson method) in Haskell using arbitrary-precision rational numbers.

Given a continuous (real) function $f : \mathbb{R} \to \mathbb{R}$ and $x_0$ , an initial approximation of the zero of function $f$ , we then obtain the next approximation using the following recurrence relation

$x_{k+1} = x_k - \displaystyle\frac{f (x_k)}{f' (x_k)}$

where $f'$ is the first derivative of $f$ . We will use arbitrary-precision rational numbers (represented as a ratio of two Integer values)

type Rational = Ratio Integer

which are defined in the Data.Ratio library.

__________

Example

Suppose we would like to find a rational approximation of $\sqrt{2}$ . We create a real function defined by $f (x) = x^2 - 2$ , whose zeros are $\sqrt{2}$ and $-\sqrt{2}$ . Note that the first derivative of $f$ is $f' (x) = 2 x$ . The initial approximation is, say, $x_0 = 1 / 1$ , which is closer to $\sqrt{2}$ than to $-\sqrt{2}$ . Hopefully, the sequence $\{x_k\}$ will converge to $\sqrt{2}$ instead of converging to $-\sqrt{2}$ . We are performing a numerical experiment, and success is not guaranteed!

The following Haskell script implements Newton’s method:

import Data.Ratio

-- define function f
f :: Rational -> Rational
f x = x*x - 2

-- define 1st derivative of function f
f' :: Rational -> Rational
f' x = 2*x

-- define Newton map
g :: Rational -> Rational
g x = x - (f x / f' x)

-- initial approximation
x0 :: Rational
x0 = 1 % 1

-- list of rational approximations
xs :: [Rational]
xs = iterate g x0

where we used (higher-order) function iterate to create the list of rational approximations. We run the script above in GHCi and use take to compute the first few rational approximations in the list:

*Main> take 6 xs
[1 % 1,3 % 2,17 % 12,577 % 408,665857 % 470832,
886731088897 % 627013566048]

Hence, we have, for instance, the following rational approximation

$x_5 = \displaystyle\frac{886731088897}{627013566048} \approx \sqrt{2}$ .

How good is this rational approximation? Let us see:

*Main> let x5 = xs !! 5
*Main> x5*x5 - 2
1 % 393146012008229658338304
*Main> 886731088897 / 627013566048
1.4142135623730951
*Main> sqrt 2
1.4142135623730951

Fairly good indeed! And all it took was five iterations!

__________

References

[1] Richard W. Hamming, Numerical Methods for Scientists and Engineers, Dover Publications, 1973.

Tags:Arbitrary-Precision Arithmetic, Data.Ratio, Haskell, Newton’s Method, Numerical Methods, Rational Approximations, Rational Arithmetic, Real Functions
Posted in Haskell, Numerical Methods | 10 Comments »

Fair play

March 31, 2012

Last February’s Ponder This challenge was the following:

To decide who would play first in a human vs. computer game, the human suggested to flip a coin it produced from its pocket, stating “heads you win, tails I win.” The computer replied, “Humans are very devious. I know that your coin is not fair, and that the probability of heads on that coin is slightly less than one half. To make this perfectly fair, flip the coin repeatedly, and I win if the coin first shows heads on toss number 1, 14, 15, 19, 20, or 23. You win if it first shows heads on any other toss.”

If the computer is correct and $p$ is the probability that the coin shows heads, give the best rational approximation to $p$ with a denominator having fewer than 10 digits.

Here is the solution.

__________

My solution #1:

Let $\mathbb{P} (H) = p$ be the probability that the coin will land with the heads side up. If the coin is biased in favor of the human player, then $p < 1/2$ . The probability that the coin toss will first produce “heads” on the $n$ -th trial (where $n \geq 1$ ) is $(1-p)^{n-1} p$ . Let us define $\mathcal{I} := \{1, 14, 15, 19, 20, 23\}$ . The probability that the computer will win is thus

$\displaystyle \sum_{n \in \mathcal{I}} (1-p)^{n-1} p$ .

We now assume that the computer knows the exact value of $p$ and, thus, is able to compute its probability of winning. Since the computer is interested in making this game “perfectly fair”, then his probability of winning should equal the human’s probability of winning, i.e., it should equal $1/2$ . Hence, we obtain the equation

$p + (1-p)^{13} p + (1-p)^{14} p + (1-p)^{18} p + (1-p)^{19} p +(1-p)^{22} p = \frac{1}{2}$

which we can solve using the following Python + SymPy script:

from sympy import *

# create symbolic variable
p = Symbol('p')

# solve polyomial equation
f = p + p*(1-p)**13+p*(1-p)**14+p*(1-p)**18+p*(1-p)**19+p*(1-p)**22
Solutions = solve(f-0.5,p)

# find (purely) real solutions
RealSols = filter(lambda z: im(z)==0, Solutions)

# print solutions
print "\nAll solutions:"
for sol in Solutions:
    print sol

# print real solutions
print "\nReal solutions:"
for sol in RealSols:
	print sol

This script outputs the following list of solutions:

All solutions:
0.334938061741437 - 1.03291350457235*I
0.334938061741437 + 1.03291350457235*I
1.97217279050061 + 0.143849563303172*I
1.50662666735084 - 0.797180194029411*I
1.92419089868505 + 0.454390584787364*I
0.0780115260218319 + 0.464383156442821*I
0.00197767511752256 - 0.101887310197153*I
1.27721993255011 + 0.951650156864179*I
1.27721993255184 - 0.951650156863701*I
0.247036637335883 - 0.624592516289942*I
0.625456509765409 - 0.845921918004056*I
0.0780115260218319 - 0.464383156442821*I
0.00197767511752256 + 0.101887310197153*I
0.991590970537258 - 0.923668626671437*I
1.79082570892033 - 0.599036471538201*I
1.92419089870934 - 0.454390584808249*I
1.79082570891289 + 0.599036471546724*I
0.499905242928390
0.6254565097654 + 0.845921918004058*I
0.991590970537348 + 0.923668626671824*I
0.247036637335883 + 0.624592516289942*I
1.50662666734992 + 0.797180194030292*I
1.97217279048996 - 0.14384956326771*I

Real solutions:
0.499905242928390

Hence, we have that the probability of heads is

$p = 0.499905242928390$ .

We can convert this number to a ratio of integers in Haskell using function approxRational in the library Data.Ratio:

import Data.Ratio

-- probability of heads
p = 0.499905242928390

-- create (infinite) list of epsilons
epsilons = map (10**) [-1,-2..]

-- create (infinite) list of ratios
ratios = map (approxRational p) epsilons

-- list of ratios whose denominators have less than 10 digits
ratios' = takeWhile (\x -> denominator x < 10^10) ratios

Running the script above in GHCi, we obtain a list of ratios:

*Main Data.Ratio> ratios'
[1 % 2,1 % 2,1 % 2,1 % 2,2386 % 4773,2611 % 5223,2636 % 5273,
2638 % 5277,13189 % 26383,44843 % 89703,166183 % 332429,
393036 % 786221,1405961 % 2812455,6243733 % 12489833,
14906352 % 29818355,69693988 % 139414397]

and we finally obtain the following rational approximation

$p \approx \displaystyle\frac{69693988}{139414397}$

whose denominator has nine digits. According to the webmaster, the rational approximation I presented above is not the best one. Hence, let us now try to obtain a better one.

__________

My solution #2:

Most likely, the reason why I did not obtain the best rational approximation is that the real solution I obtained was not precise enough. Hence, let us use the following MATLAB command to solve the polynomial equation:

solve('p + p*(1-p)^13+p*(1-p)^14+p*(1-p)^18+p*(1-p)^19+p*(1-p)^22 = 0.5')

This command produces the following list of solutions:

ans =

 .19776751175225606651411342151624e-2-.10188731019715301414082803578298*i
 .19776751175225606651411342151624e-2+.10188731019715301414082803578298*i
 .78011526021831885333432975572559e-1-.46438315644282071005250209738747*i
 .78011526021831885333432975572559e-1+.46438315644282071005250209738747*i
    .24703663733588276238861533742100-.62459251628994218281562354280746*i
    .24703663733588276238861533742100+.62459251628994218281562354280746*i
    .33493806174143698737516495548579-1.0329135045723528674007841220342*i
    .33493806174143698737516495548579+1.0329135045723528674007841220342*i
                                        .49990524292838950452962194522516
    .62545650976540488339104798827398-.84592191800405765193777444233924*i
    .62545650976540488339104798827398+.84592191800405765193777444233924*i
    .99159097053730697830960408610308-.92366862667162608535284662817351*i
    .99159097053730697830960408610308+.92366862667162608535284662817351*i
    1.2772199325509563050241902871670-.95165015686389448554291677056666*i
    1.2772199325509563050241902871670+.95165015686389448554291677056666*i
    1.5066266673486985232104204448828-.79718019402868789409470957216463*i
    1.5066266673486985232104204448828+.79718019402868789409470957216463*i
    1.7908257089204728277307542114304-.59903647154154201043833983995659*i
    1.7908257089204728277307542114304+.59903647154154201043833983995659*i
    1.9241908987061350990877558129099-.45439058479360516453156947604463*i
    1.9241908987061350990877558129099+.45439058479360516453156947604463*i
    1.9721727904901564352190617939256-.14384956327517564484908725760533*i
    1.9721727904901564352190617939256+.14384956327517564484908725760533*i

We now obtain a much more precise real solution

$p =0.49990524292838950452962194522516$ .

We modify the Haskell script, using the new value of $p$ and a much finer list of epsilons (the precisions):

import Data.Ratio

-- probability of heads
p = 0.49990524292838950452962194522516

-- create (infinite) list of epsilons
epsilons = map ((1.005)**) [-1,-2..]

-- create (infinite) list of ratios
ratios = map (approxRational p) epsilons

-- list of ratios whose denominators have less than 10 digits
ratios' = takeWhile (\x -> denominator x < 10^10) ratios

Which yields the following rational approximation

$p \approx \displaystyle\frac{61031369}{122085875}$

whose denominator has nine digits. Although this rational approximation does not match the one in the official solution, I still got my name on the “people who answered correctly” list. Surprisingly, the value of $p$ which I obtained using MATLAB is quite different from the value of $p$ used by the webmaster

$p = 0.499905242928506776611191007553$ .

Which value of $p$ is “more correct”? I do not know. Do you?

Tags:Data.Ratio, Haskell, Ponder This, Probability Theory, Puzzles, Python, SymPy
Posted in Haskell, Puzzles, Python | Leave a Comment »

Deciding the bijectivity of finite functions

March 31, 2012

Consider a function $f : \mathcal{X} \to \mathcal{Y}$ . Function $f$ is bijective if and only if it is both injective and surjective. We say that $f$ is a finite function if and only if both $\mathcal{X}$ and $\mathcal{Y}$ are finite sets.

In this post, we will restrict our attention to finite functions. For finite functions, we already know how to decide injectivity and surjectivity. Hence, deciding the bijectivity of finite functions is now trivial. In Haskell, we create the following three predicates:

isInjective :: (Eq a, Eq b) => (a -> b) -> [a] -> Bool
isInjective f xs = all phi [(x1,x2) | x1 <- xs, x2 <- xs]
                   where phi (x1,x2) = (f x1 /= f x2) || (x1 == x2)

isSurjective :: Eq b => (a -> b) -> [a] -> [b] -> Bool
isSurjective f xs ys = all psi ys
                       where psi y = or [(f x == y) | x <- xs]

isBijective :: (Eq a, Eq b) => (a -> b) -> [a] -> [b] -> Bool
isBijective f xs ys = (isInjective f xs) && (isSurjective f xs ys)

Note that predicate isInjective takes as inputs a function and a list (the domain), whereas predicate isSurjective takes as inputs a function and two lists (the domain and the codomain). Both return either True or False. Predicate isBijective is defined using the conjunction of the other two predicates. In this implementation, we separated the decision procedure from the definition of $f$ .

__________

Example #1

Let us define $\mathbb{Z}_4 := \{0, 1, 2, 3\}$ . Consider the finite function

$\begin{array}{rl} f : \mathbb{Z}_4 &\to \mathbb{Z}_4\\ n &\mapsto 3 n \pmod{4}\end{array}$

where $\pmod{4}$ denotes modulo 4 arithmetic. We know that this function is both injective and surjective. Hence, it is bijective. Here’s a GHCi session (after running the Haskell script above):

*Main> let f n = (3 * n) `mod` 4
*Main> isInjective f [0..3]
True
*Main> isSurjective f [0..3] [0..3]
True
*Main> isBijective f [0..3] [0..3]
True

__________

Example #2

Consider now the following finite function

$\begin{array}{rl} g : \mathbb{Z}_4 &\to \mathbb{Z}_4\\ n &\mapsto 2 n \pmod{4}\end{array}$

We already know that function $g$ is neither injective nor surjective. Hence, it is not bijective. Here’s a GHCi session:

*Main> let g n = (2 * n) `mod` 4
*Main> isInjective g [0..3]
False
*Main> isSurjective g [0..3] [0..3]
False
*Main> isBijective g [0..3] [0..3]
False

Tags:Bijectivity, Decision Problems, Decision Procedures, Finite Functions, Functionology, Haskell, Injectivity, Surjectivity
Posted in Haskell | Leave a Comment »

Rod Carvalho

Archive for the ‘Programming’ Category

Digraphs in Haskell

Newton’s method using rational arithmetic

Fair play

Deciding the bijectivity of finite functions

Pages

Categories

Top Posts

Recent Posts

Recent Comments

Tag Cloud

Archives

Blog Stats

Artists

Biology

Blogs

Companies

Haskell

Math Blogs

Mathematics

MATLAB

Optimization

Physics

Python

Robotics

Science

Software

Symbolic Computation

Technology

Powered by FeedBurner

Meta

Follow “Rod Carvalho”

May 2012
S	M	T	W	T	F	S
« Apr
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Rod Carvalho

Archive for the ‘Programming’ Category

Perfect shuffles in Haskell

Digraphs in Haskell

Newton’s method using rational arithmetic

Fair play

Deciding the bijectivity of finite functions

Pages

Categories

Top Posts

Recent Posts

Recent Comments

Tag Cloud

Archives

Blog Stats

Artists

Biology

Blogs

Companies

Haskell

Math Blogs

Mathematics

MATLAB

Optimization

Physics

Python

Robotics

Science

Software

Symbolic Computation

Technology

Category Cloud

Powered by FeedBurner

Meta

Follow “Rod Carvalho”