Generating all words over an alphabet

An alphabet is a finite set of symbols. A word of length over an alphabet is a sequence of symbols from , i.e.,

Alternatively, we can view a word of length over the alphabet as an -tuple (i.e., an ordered list with elements) over , i.e., . The set of all finite words over , including the empty word , is denoted by , where is the Kleene star.

We thus encounter the following problem:

Problem: Given an alphabet , how do we generate all the words over ? In other words, given , how do we generate the Kleene closure ?

The following Haskell script solves this problem:

g :: [a] -> [[a]] -> [[a]]
g alphabet = concat . map (\xs -> [ xs ++ [s] | s <- alphabet])

allwords :: [a] -> [[a]]
allwords alphabet = concat $ iterate (g alphabet) [[]]

where alphabet must be a finite list, otherwise the execution of the script won’t ever terminate. The script above, although short, uses a lot of machinery: list comprehension, higher-order functions map and iterate, concatenation of lists of lists, and partial function application. Let us test this script. First, we load it into GHCi. Then we can run a GHCi session:

*Main> -- define alphabet
*Main> let alphabet = [0,1]
*Main> -- define function f
*Main> let f = g alphabet
*Main> -- check type
*Main> :t f
f :: [[Integer]] -> [[Integer]]
*Main> -- apply f to several lists of lists
*Main> f [[]]
[[0],[1]]
*Main> (f . f) [[]]
[[0,0],[0,1],[1,0],[1,1]]
*Main> (f . f . f) [[]]
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]

So far, so good. Suppose that we would like to find all words over alphabet whose length is less than or equal to . How many such words are there? There are words of length . Hence, there are

binary words of length less than or equal to . Hence, if we make , then we obtain . Continuing our GHCi session:

*Main> take 31 $ allwords alphabet
[[],[0],[1],
[0,0],[0,1],[1,0],[1,1],
[0,0,0],[0,0,1],[0,1,0],[0,1,1],
[1,0,0],[1,0,1],[1,1,0],[1,1,1],
[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,0,1,1],
[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],
[1,0,0,0],[1,0,0,1],[1,0,1,0],[1,0,1,1],
[1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1]]

Very nice! We could use this in Coding Theory! For example, suppose that we would like to find all binary words of length whose Hamming weight is equal to . There are

such words. We can find them as follows:

*Main> -- take all words of length less than or equal to 8
*Main>  let words = take 511 $ allwords alphabet
*Main> -- filter out binary words of length 8
*Main> let wordsL8 = filter (\xs -> length xs == 8) words
*Main> length wordsL8
256
*Main> -- filter out binary words of length 8
*Main> -- and also of Hamming weight equal to 5
*Main> let wordsL8H5 = filter (\xs -> sum xs == 5) wordsL8
*Main> length wordsL8H5
56
*Main> wordsL8H5
[[0,0,0,1,1,1,1,1],[0,0,1,0,1,1,1,1],[0,0,1,1,0,1,1,1],
 [0,0,1,1,1,0,1,1],[0,0,1,1,1,1,0,1],[0,0,1,1,1,1,1,0],
 [0,1,0,0,1,1,1,1],[0,1,0,1,0,1,1,1],[0,1,0,1,1,0,1,1],
 [0,1,0,1,1,1,0,1],[0,1,0,1,1,1,1,0],[0,1,1,0,0,1,1,1],
 [0,1,1,0,1,0,1,1],[0,1,1,0,1,1,0,1],[0,1,1,0,1,1,1,0],
 [0,1,1,1,0,0,1,1],[0,1,1,1,0,1,0,1],[0,1,1,1,0,1,1,0],
 [0,1,1,1,1,0,0,1],[0,1,1,1,1,0,1,0],[0,1,1,1,1,1,0,0],
 [1,0,0,0,1,1,1,1],[1,0,0,1,0,1,1,1],[1,0,0,1,1,0,1,1],
 [1,0,0,1,1,1,0,1],[1,0,0,1,1,1,1,0],[1,0,1,0,0,1,1,1],
 [1,0,1,0,1,0,1,1],[1,0,1,0,1,1,0,1],[1,0,1,0,1,1,1,0],
 [1,0,1,1,0,0,1,1],[1,0,1,1,0,1,0,1],[1,0,1,1,0,1,1,0],
 [1,0,1,1,1,0,0,1],[1,0,1,1,1,0,1,0],[1,0,1,1,1,1,0,0],
 [1,1,0,0,0,1,1,1],[1,1,0,0,1,0,1,1],[1,1,0,0,1,1,0,1],
 [1,1,0,0,1,1,1,0],[1,1,0,1,0,0,1,1],[1,1,0,1,0,1,0,1],
 [1,1,0,1,0,1,1,0],[1,1,0,1,1,0,0,1],[1,1,0,1,1,0,1,0],
 [1,1,0,1,1,1,0,0],[1,1,1,0,0,0,1,1],[1,1,1,0,0,1,0,1],
 [1,1,1,0,0,1,1,0],[1,1,1,0,1,0,0,1],[1,1,1,0,1,0,1,0],
 [1,1,1,0,1,1,0,0],[1,1,1,1,0,0,0,1],[1,1,1,1,0,0,1,0],
 [1,1,1,1,0,1,0,0],[1,1,1,1,1,0,0,0]]

where we used function take (again) and higher-order function filter. The two predicates were built using anonymous functions.

I am happy with this script. Please let me know in case you are not.

__________

Related:

• Distance between two words (2009)

My implementation of (!!)

In Haskell we can easily create a list and then access its elements using the (!!) function, which is defined in the Prelude. Here is a very brief GHCi session:

Prelude> let xs = [7,8,9]
Prelude> xs !! 0
7
Prelude> xs !! 1
8
Prelude> xs !! 2
9

So far, so good. What if the index is negative or equals / exceeds the list’s length? Let’s see what happens in those cases:

Prelude> xs !! (-1)
*** Exception: Prelude.(!!): negative index

Prelude> xs !! 3
*** Exception: Prelude.(!!): index too large

As expected, we get error messages. What if we used the Maybe data type to avoid exceptions? This is exercise 4 in chapter 3 of O’Donnell & Hall & Page [1], which is phrased as follows:

Write (!!), a function that takes a natural number and a list and selects the th element of the list. List elements are indexed from , not , and since the type of the incoming number does not prevent it from being out of range, the result should be a Maybe type.

The aforementioned authors propose the following implementation:

import Prelude hiding ((!!))

(!!) :: Int -> [a] -> Maybe a
(!!) n [] = Nothing
(!!) 0 (x:xs) = Just x
(!!) n (x:xs) = (!!) (n-1) xs

where I added the import line to hide the standard (!!) function that is defined in the Prelude. My first thought was that the authors switched the function arguments, which makes the function look silly. Let’s give it a try. Here’s another GHCi session:

*Main> let xs = [7,8,9]
*Main> 0 !! xs
Just 7
*Main> 1 !! xs
Just 8
*Main> 2 !! xs
Just 9
*Main> (-1) !! xs
Nothing
*Main> 3 !! xs
Nothing

It appears to be working, but specifying the index before the list looks rather ugly. Wait, what if the index is negative? For example, why does (-3) !! xs return Nothing? Let’s use equational reasoning to find out:

(-3) !! [7,8,9] = (-4) !! [8,9] = 
                = (-5) !! [9] =
                = (-6) !! [] = 
                = Nothing

This reveals a fatal flaw in the authors’ implementation: if the list is infinite, then the recursion will never terminate. For example, (-1) !! [0..] will never terminate, because when the initial index is negative, decrementing the index will never get us to the zero index.

Therefore, I propose the following implementation:

import Prelude hiding ((!!))

(!!) :: [a] -> Integer -> Maybe a
(!!)     [] n = Nothing
(!!) (x:xs) n | n > 0  = (!!) xs (n-1)
              | n == 0 = Just x
              | n < 0  = Nothing

where the first argument is now a list, and the second argument an integer. Note that I used indices of type Integer (“mathematical integers”), instead of type Int (“computer integers”). Let’s see if this implementation works:

*Main> let xs = [7,8,9]
*Main> xs !! 0
Just 7
*Main> xs !! 1
Just 8
*Main> xs !! 2
Just 9
*Main> xs !! (-1)
Nothing
*Main> xs !! 3
Nothing

It appears to be working. No errors. No exceptions. If you, dear reader, happen to be acquainted with Haskell you will almost certainly be shocked (!!!), for this function is trivial! Well, that is true, but I allow myself to be intrigued by trivialities. Moreover, this function is simple enough to allow us to use equational reasoning. For example, let’s compute xs !! 2 using equational reasoning:

[7,8,9] !! 2 = [8,9] !! 1 = [9] !! 0 = Just 9

What if the index is too large? Let’s compute xs !! 4 then:

[7,8,9] !! 4 = [8,9] !! 3 = [9] !! 2 = [] !! 1 = Nothing

Step by step, by successively removing the head of the list, we get where we want to. Unfortunately, this suggests that accessing an arbitrary element of the list will not be .

__________

References

[1] John O’Donnell, Cordelia Hall, Rex Page, Discrete Mathematics using a Computer (2nd edition), Springer, 2006.

Perfect shuffles in Haskell

Consider a deck of cards. There exists a bijection from the set of cards to the finite set , which allows us to represent the deck using a ()-tuple, as follows

where the first element represents the card at the top of the deck, and the ()-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

,

whereas after a perfect out shuffle the deck will be

.

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 cards (i.e., ). 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 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.

Feedback systems in Haskell

We recently studied the first-order causal LTI system which is described by the difference equation , where . The system can be represented by the block diagram

Observing the block diagram, we conclude that there are three basic operations: addition, multiplication by a constant coefficient, and delay. We arrive at the same conclusion if we rewrite the difference equation in the form . Do note that the output is obtained by adding the input to a scaled and delayed version of the output and, therefore, we have a feedback system.

The system’s input-output relationship can be written as follows

where is the unit-delay operator. Note that we have signals rather than signal samples on both sides of the equation. To clarify, when I say “sample”, I mean the value of the signal at some (discrete) time instant. Let us introduce the linear operator such that the output signal can be written as a function of the input, , assuming zero initial condition. Hence, we obtain . It would be convenient to introduce also a gain operator to carry out the multiplication by a constant coefficient, i.e., . Composing the operators, we finally obtain the following equation

which we will now implement in Haskell.

__________

Implementation in Haskell

Our first implementation of the LTI system under study relied on state-space models and the scanl trick to propagate the initial state forwards in time. Our second implementation was little more than a beautified version of the first one. This third implementation will be radically different from the previous two.

Let us start with the following type synonyms:

type Signal a = [a]
type System a b = Signal a -> Signal b

which hopefully will make the code more readable. We build a function that takes two discrete-time signals (of the same type) and returns their elementwise addition:

(.+) :: Num a => Signal a -> Signal a -> Signal a
(.+) = zipWith (+)

Since we represent discrete-time signals as lists, the function above merely adds two lists elementwise. Let us test this function:

*Main> -- create test input signals
*Main> let us = repeat 1.0 :: Signal Float
*Main> let vs = [1..] :: Signal Float
*Main> -- add two signals elementwise
*Main> let ys = us .+ vs
*Main> take 10 ys
[2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0]
*Main> -- check types
*Main> :type (us,vs,ys)
(us,vs,ys) :: (Signal Float, Signal Float, Signal Float)

We now implement the unit-delay with zero initial condition:

delay :: Num a => System a a
delay us = 0 : us

which right-shifts the input list and introduces a zero at the output list’s head. If we want a unit-delay operator with non-zero initial condition, we would have the following code instead:

delay :: Num a => System a a
delay us = ini : us

where ini is the initial condition of the delay block. Lastly, we create the gain operator:

gain :: Num a => a -> System a a
gain alpha = map (alpha*)

which takes a number (the gain factor) and returns a system (that maps signals to signals). Note that we use partial function application. One can think of the gain operator as a function that takes a number and a signal and returns a signal. If we fix the first argument (the gain factor), we obtain a function that maps signals to signals, i.e., a system. Here is a quick test of the delay and gain operators:

*Main> -- create signal
*Main> let xs = [1..] :: Signal Float
*Main> -- delay signal
*Main> let ys = delay xs
*Main> take 10 ys
[0.0,1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0]
*Main> -- amplify delayed signal
*Main> let zs = gain 2.0 ys
*Main> take 10 zs
[0.0,2.0,4.0,6.0,8.0,10.0,12.0,14.0,16.0,18.0]

Finally, we have the following Haskell script:

type Signal a = [a]
type System a b = Signal a -> Signal b

-- signal adder
(.+) :: Num a => Signal a -> Signal a -> Signal a
(.+) = zipWith (+)

-- delay operator
delay :: Num a => System a a
delay us = 0 : us

-- gain operator
gain :: Num a => a -> System a a
gain alpha = map (alpha*)

-- build feedback system
sys :: Floating a => System a a
sys us = us .+ (gain 0.5 . delay . sys) us

where we used . Note that the last line is a direct translation of the equation to Haskell! Beautiful!

To finalize, let us obtain the impulse response of the LTI system under study for :

*Main> -- create unit impulse
*Main> let delta = 1.0 : repeat 0.0 :: Signal Float
*Main> -- compute impulse response
*Main> let hs = sys delta
*Main> take 8 hs
[1.0,0.5,0.25,0.125,6.25e-2,3.125e-2,1.5625e-2,7.8125e-3]

which is the expected impulse response for . Frankly, I am in awe. It is amazing that this implementation works!

Cascading systems in Haskell

Last weekend we learned how to build systems (LTI or otherwise) using Haskell. We now want to construct interconnections of systems. In this post we will study the series interconnection of systems, usually known as cascade interconnection. Parallel and feedback interconnections will be discussed in future posts.

__________

Cascading two LTI systems

Let us consider the series interconnection of two causal discrete-time LTI systems, and , as depicted below

where and are the outputs of each LTI system in the cascade. Since the output of system is the input of system , we have .

What LTI systems should we consider? Let us choose the simplest ones: the accumulator and the differentiator. Thus, let be an accumulator (also known as “discrete-time integrator”), whose input-output relationship is as follows

,

and let be a first difference operator (also known as “discrete-time differentiator”), whose input-output relationship is

.

Note that the output of the cascade of these two LTI systems is thus

and, hence, the cascade is input-output equivalent to the identity operator. Since for all signals , we say that is the left-inverse of system . Since both systems are LTI, the operators commute, i.e., and, therefore, is also the right-inverse of system . Since is the left- and right-inverse of , we say that is the inverse of system (and vice-versa). Do keep in mind, however, that not all systems are invertible. For details, take a look at Oppenheim & Willsky [1].

__________

Implementation in Haskell

We can easily find a state-space realization for the accumulator, but that will not be necessary. As in previous posts, let us view discrete-signals as lists. Thus, the accumulator takes a list , and returns the following list

where we assume that the initial condition of the accumulator is zero (i.e., ). Instead of using scanl yet once again (which would require us to drop the head of the list), let us now use scanl1 to implement the accumulator:

acc :: Num a => System a a
acc = scanl1 (+)

Please note that if the initial condition of the accumulator is not zero, we should use the following code instead:

acc' :: Num a => System a a
acc' us = tail $ scanl (+) acc_ini us

where acc_ini is the initial condition of the accumulator (analogous to the constant of integration in integral calculus).

The differentiator is not a proper system [2] and, therefore, it has no state-space realization. The differentiator takes a list , and returns the following list

where we again assume that . Note the following

i.e., list is obtained by elementwise subtraction of a right-shifted version of list from list itself. Subtracting two lists elementwise can be implemented using zipWith:

diff :: Num a => System a a
diff ys = zipWith (-) ys (0 : ys)

If the initial condition of the differentiator is not zero, we should instead use the following code:

diff' :: Num a => System a a
diff' ys = zipWith (-) ys (diff_ini : ys)

where diff_ini is the initial condition of the differentiator. Piecing it all together, we finally obtain the following Haskell script:

type Signal a = [a]
type System a b = Signal a -> Signal b

-- accumulator
acc :: Num a => System a a
acc = scanl1 (+)

-- differentiator
diff :: Num a => System a a
diff ys = zipWith (-) ys (0 : ys)

-- cascade of the acc. and diff.
sys :: Num a => System a a
sys = diff . acc

Take a look at the last line. It says that cascading systems is the same as composing systems! Hence, the Haskell implementation is conceptually very close to the mathematical formulation using operators. Functional analysis meets functional programming…

We run the script above on GHCi and then play with it:

*Main> -- build unit impulse
*Main> let delta = 1.0 : repeat 0.0 :: Signal Float
*Main> -- output of the accumulator
*Main> let ys = acc delta
*Main> take 20 ys
[1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,
1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0]
*Main> -- output of the differentiator
*Main> let ws = diff ys
*Main> take 20 ws
[1.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,
0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0]
*Main> -- impulse response of the cascade
*Main> let hs = sys delta
*Main> take 20 hs
[1.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,
0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0]

The impulse response of the accumulator is the unit step. The impulse response of the cascade is the unit impulse, as we expected. The differentiator is the inverse of the accumulator, and vice-versa.

__________

References

[1] Alan V. Oppenheim, Alan S. Willsky, S. Hamid Nawab, Signals & Systems, 2nd edition, Prentice-Hall, 1997.

[2] Panos Antsaklis, Anthony Michel, A Linear Systems Primer, Birkhäuser Boston, 2007.