Functional coverage tree: Difference between revisions
m
→Python: Composition of pure functions: Reversed accidental edit
m (→Python: Composition of pure functions: Reversed accidental edit) |
|||
Line 1,576:
Mainly uses pre-existing generic functions, including '''forestFromLineIndents''', '''foldTree''' and '''fmapTree''':
{{Works with|Python|3.7}}
<lang python>
from itertools import chain, product
from functools import reduce
# main :: IO ()
def main
'''Tabular outline serialisation of a parse tree
decorated with computations of:
1. Weighted coverage of each tree node.
2. Each node's share of the total project's
remaining work.
'''
columnWidths = [31, 9, 9, 9]
delimiter = '|'
reportLines = lines(REPORT)
columnTitles = init(columnNames(delimiter)(reportLines[0]))
# SERIALISATION OF DECORATED PARSE TREE
print(titleLine(delimiter)(columnWidths)(
columnTitles + ['share of residue']
))
print(indentedLinesFromTree(' ', tabulation(columnWidths))(
# TWO COMPUTATIONS BY TRAVERSAL
withResidueShares(1.0)(
foldTree(weightedCoverage)(
# TREE FROM PARSE OF OUTLINE TEXT
fmapTree(
recordFromKeysDefaultsDelimiterAndLine(columnTitles)(
[str, float, float])(['?', 1.0, 0.0])(delimiter)
)(
forestFromLineIndents(indentLevelsFromLines(
reportLines[1:]
))[0]
)
)
)
))
# WEIGHTED COVERAGE, AND SHARE OF TOTAL RESIDUE -----------
# weightedCoverage :: Tree Dict ->
# [Tree Dict] -> Tree Dict
def weightedCoverage(x):
'''The weighted coverage of a tree node,
as a function of the weighted averages
of its children.
'''
def
cws = [(r['coverage'], r['weight']) for r in [root(x) for x in xs]]
totalWeight = reduce(lambda a, x: a + x[1], cws, 0)
return Node(dict(
x, **{
'coverage': round(reduce(
lambda a, cw: a + (cw[0] * cw[1]),
cws, x['coverage']
) / (totalWeight if 0 < totalWeight else 1), 5)
}
))(xs)
return lambda xs: go(xs)
def withResidueShares(shareOfTotal):
'''A Tree of dictionaries additionally decorated with each
node's proportion of the total project's outstanding work.
'''
def go(fraction, node):
[nodeRoot, nodeNest] = apList([root, nest])([node])
weights = [root(x)['weight'] for x in nodeNest]
siblingsTotal = sum(weights)
return Node(
insertDict('residual_share')(
round(fraction * (1 - nodeRoot['coverage']), 5)
)(nodeRoot)
)(
map(
go,
[fraction * (w / siblingsTotal) for w in weights],
nodeNest
)
)
return lambda tree: go(shareOfTotal, tree)
# OUTLINE TABULATION --------------------------------------
# tabulation :: [
def tabulation(columnWidths):
'''Indented string representation of a node
in a functional coverage tree.
'''
return lambda indent, dct: '| '.join(map(
lambda k, w: (
(indent if 10 < w else '') + str(dct.get(k, ''))
).ljust(w, ' '),
dct.keys(),
columnWidths
))
def titleLine(delimiter):
'''A string consisting of a spaced and delimited
series of upper-case column titles.
'''
return lambda columnWidths: lambda ks: (
delimiter + ' '
).join(map(
lambda k, w: k.ljust(w, ' '),
[k.upper() for k in ks],
columnWidths
))
# GENERIC AND REUSABLE FUNCTIONS --------------------------
# Node :: a -> [Tree a] -> Tree a
def Node(v):
'''Constructor for a Tree node which connects a
value of some kind to a list of zero or
more child trees.
'''
return lambda xs: {'type': 'Tree', 'root': v, 'nest': xs}
# Tuple (,) :: a -> b -> (a, b)
def Tuple(x):
'''Constructor for a pair of values,
possibly of two different types.
'''
return lambda y: (
x + (y,)
) if isinstance(x, tuple) else (x, y)
# apList (<*>) :: [(a -> b)] -> [a] -> [b]
def apList(fs):
'''The application of each of a list of functions,
to each of a list of values.
'''
return liftA2List(identity)(fs)
# columnNames :: String -> String -> [String]
def columnNames(delimiter):
'''A list of lower-case keys derived from
a header line and a delimiter character.
'''
return compose(
fmapList(compose(toLower, strip)),
splitOn(delimiter)
)
# compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
'''Composition, from right to left,
of a series of functions.
'''
return lambda x: reduce(
lambda a, f: f(a),
fs[::-1], x
)
# concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
'''A concatenated list or string over which a function f
has been mapped.
The list monad can be derived by using an (a -> [b])
function which wraps its output in a list (using an
empty list to represent computational failure).
'''
return lambda xs: (''.join if isinstance(xs, str) else list)(
chain.from_iterable(map(f, xs))
)
# div :: Int -> Int -> Int
def div(x):
'''Integer division.'''
return lambda y: x // y
def firstArrow(f):
'''A simple function lifted to one which applies
to a tuple, transforming only its first item.
'''
return lambda xy: Tuple(f(xy[0]))(
xy[1]
)
# flip :: (a -> b -> c) -> b -> a -> c
def flip(f):
'''The (curried or uncurried) function f with its
arguments reversed.
'''
return lambda a: lambda b: f(b)(a)
# fmapList :: (a -> b) -> [a] -> [b]
def fmapList(f):
'''fmap over a list.
f lifted to a function over a list.
'''
return lambda xs: [f(x) for x in xs]
# fmapTree :: (a -> b) -> Tree a -> Tree b
def fmapTree(f):
'''A new tree holding the results of
applying f to each root in
the existing tree.
'''
def go(x):
return Node(f(x['root']))(
[go(v) for v in x['nest']]
)
return lambda tree: go(tree)
# foldTree :: (a -> [b] -> b) -> Tree a -> b
def foldTree(f):
'''The catamorphism on trees. A summary
value obtained by a depth-first fold.
'''
def go(node):
return f(node['root'])([
go(x) for x in node['nest']
])
return lambda tree: go(tree)
# forestFromLineIndents :: [(Int, String)] -> [Tree String]
def forestFromLineIndents(tuples):
'''A list of trees derived from a list of lines paired
with integers giving their levels of indentation.
'''
def go(xs):
if xs:
(intIndent, txt) = xs[0]
(firstTreeLines, rest) = span(
compose(lt(intIndent), fst)
)(xs[1:])
return [Node(txt)(go(firstTreeLines))] + go(rest)
else:
return []
return go(tuples)
# fst :: (a, b) -> a
def fst(tpl):
'''First member of a pair.'''
return tpl[0]
# identity :: a -> a
def identity(x):
'''The identity function.'''
return x
# indentLevelsFromLines :: [String] -> [(Int, String)]
def indentLevelsFromLines(xs):
'''Each input line stripped of leading
white space, and tupled with a preceding integer
giving its level of indentation from 0 upwards.
'''
indentTextPairs = list(map(
compose(firstArrow(len), span(isSpace)),
xs
))
indentUnit = min(concatMap(
lambda x: [x[0]] if x[0] else []
)(indentTextPairs))
return list(map(
firstArrow(flip(div)(indentUnit)),
indentTextPairs
))
# indentedLinesFromTree :: String -> (String -> a -> String) ->
# [Tree a] -> String
def indentedLinesFromTree(strTab, f):
'''An indented line rendering of a tree, in which
the function f stringifies a root value.
'''
def go(indent):
return lambda node: [f(indent, node['root'])] + concatMap(
go(strTab + indent)
)(node['nest'])
return lambda tree: unlines(go('')(tree))
# init :: [a] -> [a]
def init(xs):
'''A list containing all the elements
of xs except the last.
'''
return xs[:-1]
# insertDict :: String -> a -> Dict -> Dict
def insertDict(k):
'''A new dictionary updated with a (k, v) pair.'''
def go(v, dct):
return dict(dct, **{k: v})
return lambda v: lambda dct: go(v, dct)
# isSpace :: Char -> Bool
# isSpace :: String -> Bool
def isSpace(s):
'''True if s is not empty, and
contains only white space.
'''
return s.isspace()
# liftA2List :: (a -> b -> c) -> [a] -> [b] -> [c]
def liftA2List(f):
'''The binary operator f lifted to a function over two
lists. f applied to each pair of arguments in the
cartesian product of xs and ys.
'''
return lambda xs: lambda ys: [
f(x)(y) for x, y in product(xs, ys)
]
# lines :: String -> [String]
def lines(s):
'''A list of strings,
(containing no newline characters)
derived from a single new-line delimited string.
'''
return s.splitlines()
# lt (<) :: Ord a => a -> a -> Bool
def lt(x):
'''True if x < y.'''
return lambda y: (x < y)
# nest :: Tree a -> [Tree a]
def nest(t):
'''Accessor function for children of tree node.'''
return t['nest'] if 'nest' in t else None
# recordFromKeysDefaultsAndLine :: String ->
# { name :: String, weight :: Float, completion :: Float }
def recordFromKeysDefaultsDelimiterAndLine(columnTitles):
'''A dictionary of key-value pairs, derived from a
delimited string, together with ordered lists of
key-names, types, default values, and a delimiter.
'''
return lambda ts: lambda vs: lambda delim: lambda s: dict(
map(
lambda k, t, v, x: (k, t(x) if x else v),
columnTitles, ts, vs,
map(strip, splitOn(delim)(s))
)
)
# root :: Tree a -> a
def root(t):
'''Accessor function for data of tree node.'''
return t['root'] if 'root' in t else None
# strip :: String -> String
def strip(s):
'''A copy of s without any leading or trailling
white space.
'''
return s.strip()
# span :: (a -> Bool) -> [a] -> ([a], [a])
def span(p):
'''The longest (possibly empty) prefix of xs
that contains only elements satisfying p,
tupled with the remainder of xs.
span p xs is equivalent to (takeWhile p xs, dropWhile p xs).
'''
def go(xs):
lng = len(xs)
return splitAt(
until(lambda i: (lng == i) or not p(xs[i]))(succ)(0)
)(xs)
return lambda xs: go(xs)
# Unimplemented <- splitOn for lists (Eq a => [a] -> [a] -> [[a]])
# splitOn :: String -> String -> [String]
def splitOn(pat):
'''A list of the strings delimited by
instances of a given pattern in s.
'''
return lambda xs: (
xs.split(pat) if isinstance(xs, str) else None
)
# splitAt :: Int -> [a] -> ([a], [a])
def splitAt(n):
'''A tuple pairing the prefix of length n
with the rest of xs.
'''
return lambda xs: (xs[0:n], xs[n:])
# succ :: Enum a => a -> a
def succ(x):
'''The successor of a value.
For numeric types, (1 +).
'''
return 1 + x if isinstance(x, int) else (
chr(1 + ord(x))
)
# toLower :: String -> String
def toLower(s):
'''String in lower case.'''
return s.lower()
# unlines :: [String] -> String
def unlines(xs):
'''A single string formed by the intercalation
of a list of strings with the newline character.
'''
return '\n'.join(xs)
# until :: (a -> Bool) -> (a -> a) -> a -> a
def until(p):
'''The result of repeatedly applying f until p holds.
The initial seed value is x.
'''
def go(f, x):
v = x
while not p(v):
v = f(v)
return v
return lambda f: lambda x: go(f, x)
# MAIN ----------------------------------------------------
if __name__ == '__main__':
REPORT = '''NAME_HIERARCHY |WEIGHT |COVERAGE |
cleaning | | |
house1 |40 | |
bedrooms | |0.25 |
bathrooms | | |
bathroom1 | |0.5 |
bathroom2 | | |
outside_lavatory | |1 |
attic | |0.75 |
kitchen | |0.1 |
living_rooms | | |
lounge | | |
dining_room | | |
conservatory | | |
playroom | |1 |
basement | | |
garage | | |
garden | |0.8 |
house2 |60 | |
upstairs | | |
bedrooms | | |
suite_1 | | |
suite_2 | | |
bedroom_3 | | |
bedroom_4 | | |
bathroom | | |
toilet | | |
attics | |0.6 |
groundfloor | | |
kitchen | | |
living_rooms | | |
lounge | | |
dining_room | | |
conservatory | | |
playroom | | |
wet_room_&_toilet | | |
garage | | |
garden | |0.9 |
hot_tub_suite | |1 |
basement | | |
cellars | |1 |
wine_cellar | |1 |
cinema | |0.75 |'''
main()</lang>
{{Out}}
<pre>NAME_HIERARCHY | WEIGHT | COVERAGE | SHARE OF RESIDUE
| |||