\subsubsection{Chords}
\seclabel{chords}

Earlier I described how to represent chords as values of type \code{Music.T}.
However, sometimes it is convenient to treat chords more abstractly.
Rather than think of a chord in terms of its actual notes,
it is useful to think of it in terms of its chord ``quality'',
coupled with the key it is played in and the particular voicing used.
For example, we can describe a chord as being a ``major triad in root
position, with root middle C''.  Several approaches have been put
forth for representing this information, and we cannot cover all of
them here.  Rather, I will describe two basic representations, leaving
other alternatives to the skill and imagination of the
reader.\footnote{For example, Forte prescribes normal forms for chords
in an atonal setting \cite{forte}.}

First, one could use a \keyword{pitch} representation, where each note is
represented as its distance from some fixed pitch.  \code{0} is the
obvious fixed pitch to use, and thus, for example, \code{[0,4,7]}
represents a major triad in root position.  The first zero is in some
sense redundant, of course, but it serves to remind us that the chord
is in ``normal form''.  For example, when forming and transforming
chords, we may end up with a representation such as \code{[2,6,9]},
which is not normalized; its normal form is in fact \code{[0,4,7]}.
Thus we define:
\begin{quote}
A chord is in \keyword{pitch normal form} if the first pitch is zero,
and the subsequent pitches are monotonically increasing.
\end{quote}

One could also represent a chord \keyword{intervalically}; i.e.~as a
sequence of intervals.  A major triad in root position, for example,
would be represented as \code{[4,3,-7]}, where the last interval
``returns'' us to the ``origin''. Like the \code{0} in the pitch
representation, the last interval is redundant, but allows us to
define another sense of normal form:
\begin{quote}
A chord is in \keyword{interval normal form} if the intervals are all
greater than zero, except for the last which must be equal to the
negation of the sum of the others.
\end{quote}
In either case, we can define a chord type as:
\begin{haskelllisting}

> module Haskore.Composition.Chord where
>
> import qualified Haskore.Music  as Music
> import qualified Haskore.Melody as Melody
> import qualified Haskore.Basic.Pitch    as Pitch
> import qualified Haskore.Basic.Interval as I
> import           Haskore.General.Utility (foldrf, )
> import           Data.Ord.HT (comparing, )
> import           Data.List.HT (viewR, )
> import           Data.List (genericLength, minimumBy, )
>
> type T = [Pitch.Relative]

\end{haskelllisting}


We might ask whether there is some advantage, computationally, of
using one of these representations over the other.  However, there is
an invertible linear transformation between them, as defined by the
following functions, and thus there is in fact little advantage of one
over the other:
\begin{haskelllisting}

> pitchToInterval :: T -> T
> pitchToInterval [] = error "pitchToInterval: Chord must be non-empty."
> pitchToInterval ch@(p:ps) =
>    zipWith (-) (ps++[p]) ch
>
> intervalToPitch :: T -> T
> intervalToPitch [] = error "intervalToPitch: Chord must be non-empty."
> intervalToPitch ch =
>    let Just (chInit, chLast) = viewR (scanl (+) 0 ch)
>    in  if chLast==0
>          then chInit
>          else error "intervalToPitch: intervals do not sum-up to zero."

\end{haskelllisting}

\begin{exercise}
Show that \code{pitchToInterval} and \code{intervalToPitch}
are \keyword{inverses} in the following sense:
for any chord \code{ch1} in pitch normal form, and
\code{ch2} in interval normal form, each of length at least two:
\begin{center}
\code{intervalToPitch (pitchToInterval ch1) = ch1}\\
\code{pitchToInterval (intervalToPitch ch2) = ch2}
\end{center}
\end{exercise}

Another operation we may wish to perform is a test for \keyword{equality}
on chords, which can be done at many levels: based only on chord
quality, taking inversion into account, absolute equality, etc.  Since
the above normal forms guarantee a unique representation, equality of
chords with respect to chord quality and inversion is simple: it is
just the standard (overloaded) equality operator on lists.  On the
other hand, to measure equality based on chord quality alone, we need
to account for the notion of an \keyword{inversion}.

Using the pitch representation, the inversion of a chord can be
defined as follows:
\begin{haskelllisting}

> pitchInvert, intervalInvert :: T -> T
> pitchInvert (0:p2:ps) = 0 : map (subtract p2) ps ++ [12-p2]
> pitchInvert _ =
>    error "pitchInvert: Pitch chord representation must start with a zero."

\end{haskelllisting}
Although we could also directly define a function to invert
a chord given in interval representation, we will simply
define it in terms of functions already defined:
\begin{haskelllisting}

> intervalInvert = pitchToInterval . pitchInvert . intervalToPitch

\end{haskelllisting}
% pitchInvert [0,4,7] => [4,7,0] => [0,3,-4] => [0,3,8]
% intervalInvert [4,3,-7] => [3,-7,4] => [3,5,4] => [3,5,-8]

We can now determine whether a chord in normal form has the same
quality (but possibly different inversion) as another chord in normal
form, as follows: simply test whether one chord is equal either to the
other chord or to one of its inversions.  Since there is only a finite
number of inversions, this is well defined.  In Haskell:
\begin{haskelllisting}

> samePitch, sameInterval :: T -> T -> Bool
> samePitch ch1 ch2 =
>  let invs = take (length ch1) (iterate pitchInvert ch1)
>  in  ch2 `elem` invs
>
> sameInterval ch1 ch2 =
>  let invs = take (length ch1) (iterate intervalInvert ch1)
>  in  ch2 `elem` invs

\end{haskelllisting}
For example, \code{samePitch [0,4,7] [0,5,9]} returns \code{True}
(since \code{[0,5,9]} is the pitch normal form for the second inversion
of \code{[0,4,7]}).


Here we provide a list of some common types of chords.

%\begin{figure}
\begin{haskelllisting}

> majorInt, minorInt, majorSeventhInt, minorSeventhInt,
>    dominantSeventhInt, minorMajorSeventhInt,
>    sustainedFourthInt :: [Pitch.Relative]

> majorInt = [I.unison, I.majorThird, I.fifth]
> minorInt = [I.unison, I.minorThird, I.fifth]

> majorSeventhInt      = [I.unison, I.majorThird, I.fifth, I.majorSeventh]
> minorSeventhInt      = [I.unison, I.minorThird, I.fifth, I.minorSeventh]
> dominantSeventhInt   = [I.unison, I.majorThird, I.fifth, I.minorSeventh]
> minorMajorSeventhInt = [I.unison, I.minorThird, I.fifth, I.majorSeventh]

> sustainedFourthInt = [I.unison, I.fourth, I.fifth]

> type Inversion = Int

> fromIntervals ::
>    [Pitch.Relative] -> Inversion -> Music.T note -> [Music.T note]
> fromIntervals int inv m =
>    let err = error ("Chord.fromInterval: inversion number "
>                       ++ show inv ++ " too large")
>    in  map (flip Music.transpose m) (zipWith const
>              (drop inv (init (int ++ map (12+) int) ++ repeat err)) int)

> major, minor, majorSeventh, minorSeventh, dominantSeventh,
>    minorMajorSeventh, sustainedFourth ::
>       Inversion -> Music.T note -> [Music.T note]

> major = fromIntervals majorInt
> minor = fromIntervals minorInt

> majorSeventh      = fromIntervals majorSeventhInt
> minorSeventh      = fromIntervals minorSeventhInt
> dominantSeventh   = fromIntervals dominantSeventhInt
> minorMajorSeventh = fromIntervals minorMajorSeventhInt

> sustainedFourth = fromIntervals sustainedFourthInt

\end{haskelllisting}
%\caption{Common chords.}
%\figlabel{chords}
%\end{figure}

We want to offer a special service:
The computer shall find out inversions for chords in a sequence
such that the overall pitch does not vary so much.

A very simple approach is to compute the ``center'' of a chord,
that is the average of all pitches.
We do now try to keep the center as close as possible to an overall trend.
This is especially easy because for a chord of $n$ notes
the change to the next inversion
moves the center of the chord by $\frac{12}{n}$ tones.

The function gets the inversion of the first and the last chord and
the list of chords represented by the base note and
the intervals of all notes of the chord.
\begin{haskelllisting}

> data Generic attr = Generic {
>    genericPitchClass :: Pitch.Class,
>    genericIntervals  :: T,
>    genericDur        :: Music.Dur,
>    genericAttr       :: attr}
>
> type Boundary = (Pitch.T, Pitch.T)
>
> generic :: Pitch.Class -> T -> Music.Dur -> attr -> Generic attr
> generic = Generic
>
> leastVaryingInversions ::
>    Boundary -> [Generic attr] -> [[Melody.T attr]]
> leastVaryingInversions (begin,end) gs =
>    let beginCenter = fromIntegral (Pitch.toInt begin)
>        endCenter   = fromIntegral (Pitch.toInt end)
>        steep = (endCenter - beginCenter) / (genericLength gs - 1)
>        trend = map (\k -> beginCenter + steep * fromIntegral k)
>                    [0 .. (length gs - 1)]
>        invs = zipWith
>                  (\g t -> round (matchingInversion g t))
>                  gs trend
>    in  zipWith genericToNotes invs gs
>
> inversionIncrement :: T -> Double
> inversionIncrement ps = 12 / genericLength ps
>
> matchingInversion :: Generic attr -> Double -> Double
> matchingInversion g dst =
>   let c = chordCenter g
>       inc = inversionIncrement (genericIntervals g)
>   in  (dst-c)/inc
>
> mean :: [Pitch.Relative] -> Double
> mean ps = sum (map fromIntegral ps) / genericLength ps
>
> chordCenter :: Generic attr -> Double
> chordCenter (Generic pc ps _ _) =
>    fromIntegral (Pitch.classToInt pc) + mean ps
>
> boundaryCenter :: (Pitch.Octave,Inversion) -> Generic attr -> Double
> boundaryCenter (oct,inv) g =
>    12 * fromIntegral oct + chordCenter g +
>       fromIntegral inv * inversionIncrement (genericIntervals g)
>
> invert :: Inversion -> T -> T
> invert inv ps =
>    let (q,r) = divMod inv (length ps)
>    in  zipWith (+) ps
>           (replicate r (12*(q+1)) ++ repeat (12*q))
>
> genericToNotes :: Inversion -> Generic attr -> [Melody.T attr]
> genericToNotes inv (Generic pc ps dur attr) =
>    map (\t -> Melody.note (Pitch.transpose t (0,pc)) dur attr)
>        (invert inv ps)

\end{haskelllisting}

A more complicated algorithm will also work for other definitions of variation.
We compute the mean pitch for every chord
and minimize the variation of the pitch.
The variation is defined here
as the sum of the squared differences of successive chords.

This leads to a shortest ways search in a graph
where each inversion of a chord is a node
and each possible neighbourhood of inversions is an edge.
The nodes for the inversions of a chord
and the nodes for the inversions of the succeeding chord
build a complete bi-partite graph.

First we write a shortest ways search algorithm
that is specialised to our problem.
In each step we process one chord.
We construct a list of inversions,
where each inversion is associated
with the optimal way from the beginning chord to this inversion
and its variation.
This list passed to the processing of the next chord.
For reasons of simplicity we process the list backwards.

The inputs of the algorithm are a distance function
and the list of concurrent inversions for each chord.
The first element of the list contains all starting inversions,
the last element contains all ending inversions.
If you want a definitive start and end inversion,
use one-element lists.
The output is the list of the optimal inversion for each chord.
More precisely it is a list of all optimal ways,
where for each starting inversion there is one optimal way
to the closest ending inversion.
\begin{haskelllisting}

> shortestWays :: (Num b, Ord b) =>
>    (a -> a -> b) -> [[a]] -> [(b,[a])]
> shortestWays dist =
>    foldrf (processZone dist) (map (\x->(0,[x])))

> processZone :: (Num b, Ord b) =>
>    (a -> a -> b) -> [a] -> [(b,[a])] -> [(b,[a])]
> processZone dist srcs ways =
>    let distToWay src (d,dst:_) = d + dist src dst
>        distToWay _   (_,[])    =
>           error "processZone: list is never empty if called from shortestWays"
>    in  map (\src -> minimumBy (comparing fst)
>               (map (\way -> (distToWay src way, src : snd way)) ways)) srcs

> propShortestWays :: Int -> Int -> Bool
> propShortestWays n k =
>    let sws = shortestWays (\x y -> (x-y)^(2::Int))
>                           (replicate n [0..(n*k)] ++ [[0]])
>    in  head sws == (0, replicate (n+1) 0)  &&
>        last sws == (n*k^(2::Int), reverse [0,k..n*k])

\end{haskelllisting}

This routine could be made more efficient
because the centers of the chords with different inversions are equidistant.

\begin{haskelllisting}

> leastVaryingInversionsSW ::
>    Boundary -> [Generic attr] -> [[Melody.T attr]]
> leastVaryingInversionsSW bnd gs =
>    let dist (_,c0) (_,c1) = (c0-c1)^(2::Int)
>        [(_,invs)] =
>           shortestWays dist
>              (inversionCenters bnd gs)
>    in  zipWith (\(inv,_) -> genericToNotes inv) invs gs
>
> inversionCenters :: Boundary -> [Generic attr] -> [[(Inversion,Double)]]
> inversionCenters (begin,end) gs =
>    let margin = 7
>        beginCenter = fromIntegral (Pitch.toInt begin)
>        endCenter   = fromIntegral (Pitch.toInt end)
>        lower = min beginCenter endCenter - margin
>        upper = max beginCenter endCenter + margin
>        inversions g =
>           let c = chordCenter g
>               inc = inversionIncrement (genericIntervals g)
>               invs :: [Inversion]
>               invs = [floor ((lower-c)/inc) ..
>                       ceiling ((upper-c)/inc)]
>           in  map (\inv -> (inv, c + inc * fromIntegral inv)) invs
>        boundInv g center =
>           (round (matchingInversion g center), center)
>    in  [[boundInv (head gs) beginCenter]] ++
>        map inversions (tail (init gs)) ++
>        [[boundInv (last gs) endCenter]]

\end{haskelllisting}



Now two helper functions for creating a harmonic and a melodic chord,
that is chords of notes of the same length
in sequentially or simultaneously.

\begin{haskelllisting}

> melodicGen, harmonicGen :: attr -> Music.Dur ->
>    [Music.Dur -> attr -> Melody.T attr] -> Melody.T attr
> melodicGen  attr d = Music.line  . map (\n -> n d attr)
> harmonicGen attr d = Music.chord . map (\n -> n d attr)

\end{haskelllisting}