{-# language TypeFamilies #-}

module Ersatz.Relation.Data (
-- * The @Relation@ type
  Relation
-- * Construction
, relation, symmetric_relation
, build
, buildFrom, buildFromM
, identity
-- * Components
, bounds, (!), indices, assocs, elems
, domain, codomain, universe
, universeSize
, is_homogeneous
, card
-- * Pretty printing
, table
)  where

import Prelude hiding ( and, (&&), any )

import Ersatz.Bit
import Ersatz.Bits ( Bits, sumBit )
import Ersatz.Codec
import Ersatz.Variable (exists)
import Ersatz.Problem (MonadSAT)

import Control.Monad (guard)
import qualified Data.Array as A
import Data.Array ( Array, Ix )


-- | @Relation a b@ represents a binary relation \(R \subseteq A \times B \),
-- where the domain \(A\) is a finite subset of the type @a@,
-- and the codomain \(B\) is a finite subset of the type @b@.
--
-- A relation is stored internally as @Array (a,b) Bit@,
-- so @a@ and @b@ have to be instances of 'Ix',
-- and both \(A\) and \(B\) are intervals.

newtype Relation a b = Relation (Array (a, b) Bit)

instance (Ix a, Ix b) => Codec (Relation a b) where
  type Decoded (Relation a b) = Array (a, b) Bool
  decode :: Solution -> Relation a b -> Maybe (Decoded (Relation a b))
decode Solution
s (Relation Array (a, b) Bit
a) = Solution -> Array (a, b) Bit -> Maybe (Decoded (Array (a, b) Bit))
forall a. Codec a => Solution -> a -> Maybe (Decoded a)
decode Solution
s Array (a, b) Bit
a
  encode :: Decoded (Relation a b) -> Relation a b
encode Decoded (Relation a b)
a = Array (a, b) Bit -> Relation a b
forall a b. Array (a, b) Bit -> Relation a b
Relation (Array (a, b) Bit -> Relation a b)
-> Array (a, b) Bit -> Relation a b
forall a b. (a -> b) -> a -> b
$ Decoded (Array (a, b) Bit) -> Array (a, b) Bit
forall a. Codec a => Decoded a -> a
encode Decoded (Array (a, b) Bit)
Decoded (Relation a b)
a


-- | @relation ((amin,bmin),(amax,mbax))@ constructs an indeterminate relation \( R \subseteq A \times B \)
-- where \(A\) is @{amin .. amax}@ and \(B\) is @{bmin .. bmax}@.
relation :: ( Ix a, Ix b, MonadSAT s m ) =>
  ((a,b),(a,b))
  -> m ( Relation a b )
relation :: forall a b s (m :: * -> *).
(Ix a, Ix b, MonadSAT s m) =>
((a, b), (a, b)) -> m (Relation a b)
relation ((a, b), (a, b))
bnd = do
    [((a, b), Bit)]
pairs <- [m ((a, b), Bit)] -> m [((a, b), Bit)]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
forall (m :: * -> *) a. Monad m => [m a] -> m [a]
sequence ([m ((a, b), Bit)] -> m [((a, b), Bit)])
-> [m ((a, b), Bit)] -> m [((a, b), Bit)]
forall a b. (a -> b) -> a -> b
$ do
        (a, b)
p <- ((a, b), (a, b)) -> [(a, b)]
forall a. Ix a => (a, a) -> [a]
A.range ((a, b), (a, b))
bnd
        m ((a, b), Bit) -> [m ((a, b), Bit)]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return (m ((a, b), Bit) -> [m ((a, b), Bit)])
-> m ((a, b), Bit) -> [m ((a, b), Bit)]
forall a b. (a -> b) -> a -> b
$ do
            Bit
x <- m Bit
forall a s (m :: * -> *). (Variable a, MonadSAT s m) => m a
exists
            ((a, b), Bit) -> m ((a, b), Bit)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ( (a, b)
p, Bit
x )
    Relation a b -> m (Relation a b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Relation a b -> m (Relation a b))
-> Relation a b -> m (Relation a b)
forall a b. (a -> b) -> a -> b
$ ((a, b), (a, b)) -> [((a, b), Bit)] -> Relation a b
forall a b.
(Ix a, Ix b) =>
((a, b), (a, b)) -> [((a, b), Bit)] -> Relation a b
build ((a, b), (a, b))
bnd [((a, b), Bit)]
pairs

-- | Constructs an indeterminate relation \( R \subseteq B \times B \)
-- that is symmetric, i.e., \( \forall x, y \in B: ((x,y) \in R) \rightarrow ((y,x) \in R) \).
symmetric_relation ::
  (MonadSAT s m, Ix b) =>
  ((b, b), (b, b)) -- ^ Since a symmetric relation must be homogeneous, the domain must equal the codomain.
                   -- Therefore, given bounds @((p,q),(r,s))@, it must hold that @p=q@ and @r=s@.
  -> m (Relation b b)
symmetric_relation :: forall s (m :: * -> *) b.
(MonadSAT s m, Ix b) =>
((b, b), (b, b)) -> m (Relation b b)
symmetric_relation ((b, b), (b, b))
bnd = do
    [[((b, b), Bit)]]
pairs <- [m [((b, b), Bit)]] -> m [[((b, b), Bit)]]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
forall (m :: * -> *) a. Monad m => [m a] -> m [a]
sequence ([m [((b, b), Bit)]] -> m [[((b, b), Bit)]])
-> [m [((b, b), Bit)]] -> m [[((b, b), Bit)]]
forall a b. (a -> b) -> a -> b
$ do
        (b
p,b
q) <- ((b, b), (b, b)) -> [(b, b)]
forall a. Ix a => (a, a) -> [a]
A.range ((b, b), (b, b))
bnd
        Bool -> [()]
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Bool -> [()]) -> Bool -> [()]
forall a b. (a -> b) -> a -> b
$ b
p b -> b -> Bool
forall a. Ord a => a -> a -> Bool
<= b
q
        m [((b, b), Bit)] -> [m [((b, b), Bit)]]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return (m [((b, b), Bit)] -> [m [((b, b), Bit)]])
-> m [((b, b), Bit)] -> [m [((b, b), Bit)]]
forall a b. (a -> b) -> a -> b
$ do
            Bit
x <- m Bit
forall a s (m :: * -> *). (Variable a, MonadSAT s m) => m a
exists
            [((b, b), Bit)] -> m [((b, b), Bit)]
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ([((b, b), Bit)] -> m [((b, b), Bit)])
-> [((b, b), Bit)] -> m [((b, b), Bit)]
forall a b. (a -> b) -> a -> b
$   ((b
p,b
q), Bit
x)
                   ((b, b), Bit) -> [((b, b), Bit)] -> [((b, b), Bit)]
forall a. a -> [a] -> [a]
: [ ((b
q,b
p), Bit
x) | b
p b -> b -> Bool
forall a. Eq a => a -> a -> Bool
/= b
q ]
    Relation b b -> m (Relation b b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Relation b b -> m (Relation b b))
-> Relation b b -> m (Relation b b)
forall a b. (a -> b) -> a -> b
$ ((b, b), (b, b)) -> [((b, b), Bit)] -> Relation b b
forall a b.
(Ix a, Ix b) =>
((a, b), (a, b)) -> [((a, b), Bit)] -> Relation a b
build ((b, b), (b, b))
bnd ([((b, b), Bit)] -> Relation b b)
-> [((b, b), Bit)] -> Relation b b
forall a b. (a -> b) -> a -> b
$ [[((b, b), Bit)]] -> [((b, b), Bit)]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[((b, b), Bit)]]
pairs

-- | Constructs a relation \(R \subseteq A \times B \) from a list.
--
-- ==== __Example__
--
-- @
-- r = build ((0,'a'),(1,'b')) [ ((0,'a'), true), ((0,'b'), false)
--                         , ((1,'a'), false), ((1,'b'), true) ]
-- @
build :: ( Ix a, Ix b )
      => ((a,b),(a,b))
      -> [ ((a,b), Bit ) ] -- ^ A list of tuples, where the first element represents an element
                           -- \( (x,y) \in A \times B \) and the second element is a positive 'Bit'
                           -- if \( (x,y) \in R \), or a negative 'Bit' if \( (x,y) \notin R \).
      -> Relation a b
build :: forall a b.
(Ix a, Ix b) =>
((a, b), (a, b)) -> [((a, b), Bit)] -> Relation a b
build ((a, b), (a, b))
bnd [((a, b), Bit)]
pairs = Array (a, b) Bit -> Relation a b
forall a b. Array (a, b) Bit -> Relation a b
Relation (Array (a, b) Bit -> Relation a b)
-> Array (a, b) Bit -> Relation a b
forall a b. (a -> b) -> a -> b
$ ((a, b), (a, b)) -> [((a, b), Bit)] -> Array (a, b) Bit
forall i e. Ix i => (i, i) -> [(i, e)] -> Array i e
A.array ((a, b), (a, b))
bnd [((a, b), Bit)]
pairs

-- | Constructs a relation \(R \subseteq A \times B \) from a function.
buildFrom :: (Ix a, Ix b)
          => ((a,b),(a,b))
          -> ((a,b) -> Bit) -- ^ A function that assigns a 'Bit'-value
                            -- to each element \( (x,y) \in A \times B \).
          -> Relation a b
buildFrom :: forall a b.
(Ix a, Ix b) =>
((a, b), (a, b)) -> ((a, b) -> Bit) -> Relation a b
buildFrom ((a, b), (a, b))
bnd (a, b) -> Bit
p = ((a, b), (a, b)) -> [((a, b), Bit)] -> Relation a b
forall a b.
(Ix a, Ix b) =>
((a, b), (a, b)) -> [((a, b), Bit)] -> Relation a b
build ((a, b), (a, b))
bnd ([((a, b), Bit)] -> Relation a b)
-> [((a, b), Bit)] -> Relation a b
forall a b. (a -> b) -> a -> b
$ (((a, b) -> ((a, b), Bit)) -> [(a, b)] -> [((a, b), Bit)])
-> [(a, b)] -> ((a, b) -> ((a, b), Bit)) -> [((a, b), Bit)]
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a, b) -> ((a, b), Bit)) -> [(a, b)] -> [((a, b), Bit)]
forall a b. (a -> b) -> [a] -> [b]
map (((a, b), (a, b)) -> [(a, b)]
forall a. Ix a => (a, a) -> [a]
A.range ((a, b), (a, b))
bnd) (((a, b) -> ((a, b), Bit)) -> [((a, b), Bit)])
-> ((a, b) -> ((a, b), Bit)) -> [((a, b), Bit)]
forall a b. (a -> b) -> a -> b
$ \ (a, b)
i -> ((a, b)
i, (a, b) -> Bit
p (a, b)
i)

-- | Constructs an indeterminate relation \(R \subseteq A \times B\) from a function.
buildFromM :: (Ix a, Ix b, MonadSAT s m)
          => ((a,b),(a,b))
          -> ((a,b) -> m Bit)
          -> m (Relation a b)
buildFromM :: forall a b s (m :: * -> *).
(Ix a, Ix b, MonadSAT s m) =>
((a, b), (a, b)) -> ((a, b) -> m Bit) -> m (Relation a b)
buildFromM ((a, b), (a, b))
bnd (a, b) -> m Bit
p = do
    [((a, b), Bit)]
pairs <- [m ((a, b), Bit)] -> m [((a, b), Bit)]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
forall (m :: * -> *) a. Monad m => [m a] -> m [a]
sequence ([m ((a, b), Bit)] -> m [((a, b), Bit)])
-> [m ((a, b), Bit)] -> m [((a, b), Bit)]
forall a b. (a -> b) -> a -> b
$ do
        (a, b)
i <- ((a, b), (a, b)) -> [(a, b)]
forall a. Ix a => (a, a) -> [a]
A.range ((a, b), (a, b))
bnd
        m ((a, b), Bit) -> [m ((a, b), Bit)]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return (m ((a, b), Bit) -> [m ((a, b), Bit)])
-> m ((a, b), Bit) -> [m ((a, b), Bit)]
forall a b. (a -> b) -> a -> b
$ do
            Bit
x <- (a, b) -> m Bit
p (a, b)
i
            ((a, b), Bit) -> m ((a, b), Bit)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ((a, b)
i, Bit
x)
    Relation a b -> m (Relation a b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Relation a b -> m (Relation a b))
-> Relation a b -> m (Relation a b)
forall a b. (a -> b) -> a -> b
$ ((a, b), (a, b)) -> [((a, b), Bit)] -> Relation a b
forall a b.
(Ix a, Ix b) =>
((a, b), (a, b)) -> [((a, b), Bit)] -> Relation a b
build ((a, b), (a, b))
bnd [((a, b), Bit)]
pairs

-- | Constructs the identity relation \(I = \{ (x,x) ~|~ x \in A \} \subseteq A \times A\).
identity :: (Ix a)
         => ((a,a),(a,a)) -- ^ Since the identity relation is homogeneous, the domain must equal the codomain.
                          -- Therefore, given bounds @((p,q),(r,s))@, it must hold that @p=q@ and @r=s@.
         -> Relation a a
identity :: forall a. Ix a => ((a, a), (a, a)) -> Relation a a
identity ((a
a,a
b),(a
c,a
d))
    | (a
a,a
c) (a, a) -> (a, a) -> Bool
forall a. Eq a => a -> a -> Bool
== (a
b,a
d) = ((a, a), (a, a)) -> ((a, a) -> Bit) -> Relation a a
forall a b.
(Ix a, Ix b) =>
((a, b), (a, b)) -> ((a, b) -> Bit) -> Relation a b
buildFrom ((a
a,a
b),(a
c,a
d)) (\ (a
i,a
j) -> Bool -> Bit
forall b. Boolean b => Bool -> b
bool (Bool -> Bit) -> Bool -> Bit
forall a b. (a -> b) -> a -> b
$ a
i a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
j)
    | Bool
otherwise      = [Char] -> Relation a a
forall a. HasCallStack => [Char] -> a
error [Char]
"The domain must equal the codomain!"


-- | The bounds of the array that correspond to the matrix representation of the given relation.
--
-- ==== __Example__
--
-- >>> r = build ((0,0),(1,1)) [((0,0), false), ((0,1), true), ((1,0), true), ((1,1), false)]
-- >>> bounds r
-- ((0,0),(1,1))
bounds :: (Ix a, Ix b) => Relation a b -> ((a,b),(a,b))
bounds :: forall a b. (Ix a, Ix b) => Relation a b -> ((a, b), (a, b))
bounds ( Relation Array (a, b) Bit
r ) = Array (a, b) Bit -> ((a, b), (a, b))
forall i e. Array i e -> (i, i)
A.bounds Array (a, b) Bit
r

-- | The list of indices, where each index represents an element \( (x,y) \in A \times B \)
-- that may be contained in the given relation \(R \subseteq A \times B \).
--
-- ==== __Example__
--
-- >>> r = build ((0,0),(1,1)) [((0,0), false), ((0,1), true), ((1,0), true), ((1,1), false)]
-- >>> indices r
-- [(0,0),(0,1),(1,0),(1,1)]
indices :: (Ix a, Ix b) => Relation a b -> [(a, b)]
indices :: forall a b. (Ix a, Ix b) => Relation a b -> [(a, b)]
indices ( Relation Array (a, b) Bit
r ) = Array (a, b) Bit -> [(a, b)]
forall i e. Ix i => Array i e -> [i]
A.indices Array (a, b) Bit
r

-- | The list of tuples for the given relation \(R \subseteq A \times B \),
-- where the first element represents an element \( (x,y) \in A \times B \)
-- and the second element indicates via a 'Bit' , if \( (x,y) \in R \) or not.
--
-- ==== __Example__
--
-- >>> r = build ((0,0),(1,1)) [((0,0), false), ((0,1), true), ((1,0), true), ((1,1), false)]
-- >>> assocs r
-- [((0,0),Var (-1)),((0,1),Var 1),((1,0),Var 1),((1,1),Var (-1))]
assocs :: (Ix a, Ix b) => Relation a b -> [((a, b), Bit)]
assocs :: forall a b. (Ix a, Ix b) => Relation a b -> [((a, b), Bit)]
assocs ( Relation Array (a, b) Bit
r ) = Array (a, b) Bit -> [((a, b), Bit)]
forall i e. Ix i => Array i e -> [(i, e)]
A.assocs Array (a, b) Bit
r

-- | The list of elements of the array
-- that correspond to the matrix representation of the given relation.
--
-- ==== __Example__
--
-- >>> r = build ((0,0),(1,1)) [((0,0), false), ((0,1), true), ((1,0), true), ((1,1), false))]
-- >>> elems r
-- [Var (-1),Var 1,Var 1,Var (-1)]
elems :: (Ix a, Ix b) => Relation a b -> [Bit]
elems :: forall a b. (Ix a, Ix b) => Relation a b -> [Bit]
elems ( Relation Array (a, b) Bit
r ) = Array (a, b) Bit -> [Bit]
forall i e. Array i e -> [e]
A.elems Array (a, b) Bit
r

-- | The 'Bit'-value for a given element \( (x,y) \in A \times B \)
-- and a given relation \(R \subseteq A \times B \) that indicates
-- if \( (x,y) \in R \) or not.
--
-- ==== __Example__
--
-- >>> r = build ((0,0),(1,1)) [((0,0), false), ((0,1), true), ((1,0), true), ((1,1), false))]
-- >>> r ! (0,0)
-- Var (-1)
-- >>> r ! (0,1)
-- Var 1
(!) :: (Ix a, Ix b) => Relation a b -> (a, b) -> Bit
Relation Array (a, b) Bit
r ! :: forall a b. (Ix a, Ix b) => Relation a b -> (a, b) -> Bit
! (a, b)
p = Array (a, b) Bit
r Array (a, b) Bit -> (a, b) -> Bit
forall i e. Ix i => Array i e -> i -> e
A.! (a, b)
p

-- | The domain \(A\) of a relation \(R \subseteq A \times B\).
domain :: (Ix a, Ix b) => Relation a b -> [a]
domain :: forall a b. (Ix a, Ix b) => Relation a b -> [a]
domain Relation a b
r =
  let ((a
x,b
_),(a
x',b
_)) = Relation a b -> ((a, b), (a, b))
forall a b. (Ix a, Ix b) => Relation a b -> ((a, b), (a, b))
bounds Relation a b
r
  in (a, a) -> [a]
forall a. Ix a => (a, a) -> [a]
A.range (a
x,a
x')

-- | The codomain \(B\) of a relation \(R \subseteq A \times B\).
codomain :: (Ix a, Ix b) => Relation a b -> [b]
codomain :: forall a b. (Ix a, Ix b) => Relation a b -> [b]
codomain Relation a b
r =
  let ((a
_,b
y),(a
_,b
y')) = Relation a b -> ((a, b), (a, b))
forall a b. (Ix a, Ix b) => Relation a b -> ((a, b), (a, b))
bounds Relation a b
r
  in (b, b) -> [b]
forall a. Ix a => (a, a) -> [a]
A.range (b
y,b
y')

-- | The universe \(A\) of a relation \(R \subseteq A \times A\).
universe :: Ix a => Relation a a -> [a]
universe :: forall a. Ix a => Relation a a -> [a]
universe Relation a a
r
  | Relation a a -> Bool
forall a. Ix a => Relation a a -> Bool
is_homogeneous Relation a a
r = Relation a a -> [a]
forall a b. (Ix a, Ix b) => Relation a b -> [a]
domain Relation a a
r
  | Bool
otherwise = [Char] -> [a]
forall a. HasCallStack => [Char] -> a
error [Char]
"Relation is not homogeneous!"

-- | The size of the universe \(A\) of a relation \(R \subseteq A \times A\).
universeSize :: Ix a => Relation a a -> Int
universeSize :: forall a. Ix a => Relation a a -> Int
universeSize Relation a a
r
  | Relation a a -> Bool
forall a. Ix a => Relation a a -> Bool
is_homogeneous Relation a a
r =
      let ((a
a,a
_),(a
c,a
_)) = Relation a a -> ((a, a), (a, a))
forall a b. (Ix a, Ix b) => Relation a b -> ((a, b), (a, b))
bounds Relation a a
r
      in (a, a) -> Int
forall a. Ix a => (a, a) -> Int
A.rangeSize (a
a,a
c)
  | Bool
otherwise = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error [Char]
"Relation is not homogeneous!"

-- | Tests if a relation is homogeneous, i.e., if the domain is equal to the codomain.
is_homogeneous :: Ix a => Relation a a -> Bool
is_homogeneous :: forall a. Ix a => Relation a a -> Bool
is_homogeneous Relation a a
r =
  let ((a
a,a
b),(a
c,a
d)) = Relation a a -> ((a, a), (a, a))
forall a b. (Ix a, Ix b) => Relation a b -> ((a, b), (a, b))
bounds Relation a a
r
  in (a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b) Bool -> Bool -> Bool
forall b. Boolean b => b -> b -> b
&& (a
c a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
d)

-- | The number of pairs \( (x,y) \in R \) for the given relation
-- \( R \subseteq A \times B \).
card :: (Ix a, Ix b) => Relation a b -> Bits
card :: forall a b. (Ix a, Ix b) => Relation a b -> Bits
card = [Bit] -> Bits
forall (t :: * -> *). Foldable t => t Bit -> Bits
sumBit ([Bit] -> Bits) -> (Relation a b -> [Bit]) -> Relation a b -> Bits
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation a b -> [Bit]
forall a b. (Ix a, Ix b) => Relation a b -> [Bit]
elems

-- | Print a satisfying assignment from a SAT solver, where the assignment is interpreted as a relation.
-- @putStrLn $ table \</assignment/\>@ corresponds to the matrix representation of this relation.
table :: (Ix a, Ix b)
      => Array (a,b) Bool -> String
table :: forall a b. (Ix a, Ix b) => Array (a, b) Bool -> [Char]
table Array (a, b) Bool
r = [[Char]] -> [Char]
unlines ([[Char]] -> [Char]) -> [[Char]] -> [Char]
forall a b. (a -> b) -> a -> b
$ do
    let ((a
a,b
b),(a
c,b
d)) = Array (a, b) Bool -> ((a, b), (a, b))
forall i e. Array i e -> (i, i)
A.bounds Array (a, b) Bool
r
    a
x <- (a, a) -> [a]
forall a. Ix a => (a, a) -> [a]
A.range (a
a,a
c)
    [Char] -> [[Char]]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return ([Char] -> [[Char]]) -> [Char] -> [[Char]]
forall a b. (a -> b) -> a -> b
$ [[Char]] -> [Char]
unwords ([[Char]] -> [Char]) -> [[Char]] -> [Char]
forall a b. (a -> b) -> a -> b
$ do
        b
y <- (b, b) -> [b]
forall a. Ix a => (a, a) -> [a]
A.range (b
b,b
d)
        [Char] -> [[Char]]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return ([Char] -> [[Char]]) -> [Char] -> [[Char]]
forall a b. (a -> b) -> a -> b
$ if Array (a, b) Bool
r Array (a, b) Bool -> (a, b) -> Bool
forall i e. Ix i => Array i e -> i -> e
A.! (a
x,b
y) then [Char]
"*" else [Char]
"."