Functional coverage tree: Difference between revisions
Content added Content deleted
Line 1,576: | Line 1,576: | ||
Mainly uses pre-existing generic functions, including '''forestFromLineIndents''', '''foldTree''' and '''fmapTree''': |
Mainly uses pre-existing generic functions, including '''forestFromLineIndents''', '''foldTree''' and '''fmapTree''': |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
<lang python> |
<lang python>{-# LANGUAGE OverloadedStrings #-} |
||
import qualified Data.Text.Read as T |
|||
from itertools import chain, product |
|||
import qualified Data.Text.IO as T |
|||
from functools import reduce |
|||
import qualified Data.Text as T |
|||
import Control.Arrow ((&&&), first) |
|||
import Numeric (showFFloat) |
|||
import Data.Char (isSpace) |
|||
import Data.Bool (bool) |
|||
import Data.Tree |
|||
data Coverage = Coverage |
|||
{ name :: T.Text |
|||
, weight :: Float |
|||
, coverage :: Float |
|||
, share :: Float |
|||
} deriving (Show) |
|||
-- TEST --------------------------------------------------- |
|||
# main :: IO () |
|||
main :: IO () |
|||
main = |
|||
'''Tabular outline serialisation of a parse tree |
|||
T.readFile "coverageOutline.txt" >>= (T.putStrLn . updatedCoverageOutline) |
|||
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 = '|' |
|||
-- UPDATED COVERAGE OUTLINE ------------------------------- |
|||
reportLines = lines(REPORT) |
|||
updatedCoverageOutline :: T.Text -> T.Text |
|||
columnTitles = init(columnNames(delimiter)(reportLines[0])) |
|||
updatedCoverageOutline s = |
|||
let delimiter = "|" |
|||
indentedLines = T.lines s |
|||
columnNames = init $ tokenizeWith delimiter (head indentedLines) |
|||
in T.unlines |
|||
[ tabulation (columnNames ++ ["SHARE OF RESIDUE"]) |
|||
, indentedLinesFromTree " " showCoverage $ |
|||
withResidueShares 1.0 $ |
|||
foldTree |
|||
weightedCoverage |
|||
(parseTreeFromOutline delimiter indentedLines) |
|||
] |
|||
-- WEIGHTED COVERAGE AND SHARES OF REMAINING WORK --------- |
|||
# SERIALISATION OF DECORATED PARSE TREE |
|||
weightedCoverage :: Coverage -> Forest Coverage -> Tree Coverage |
|||
print(titleLine(delimiter)(columnWidths)( |
|||
weightedCoverage x xs = |
|||
columnTitles + ['share of residue'] |
|||
let cws = (coverage &&& weight) <$> (rootLabel <$> xs) |
|||
)) |
|||
totalWeight = foldr ((+) . snd) 0 cws |
|||
print(indentedLinesFromTree(' ', tabulation(columnWidths))( |
|||
in Node |
|||
(x |
|||
{ coverage = |
|||
foldr (\(c, w) a -> (c * w) + a) (coverage x) cws / |
|||
bool 1 totalWeight (0 < totalWeight) |
|||
}) |
|||
xs |
|||
withResidueShares :: Float -> Tree Coverage -> Tree Coverage |
|||
# TWO COMPUTATIONS BY TRAVERSAL |
|||
withResidueShares shareOfTotal tree = |
|||
withResidueShares(1.0)( |
|||
let go fraction node = |
|||
foldTree(weightedCoverage)( |
|||
let forest = subForest node |
|||
cws = (coverage &&& weight) <$> (rootLabel <$> forest) |
|||
weights = snd <$> cws |
|||
weightTotal = sum weights |
|||
nodeRoot = rootLabel node |
|||
in Node |
|||
(nodeRoot |
|||
{ share = fraction * (1 - coverage nodeRoot) |
|||
}) |
|||
(zipWith go (((fraction *) . (/ weightTotal)) <$> weights) forest) |
|||
in go shareOfTotal tree |
|||
-- OUTLINE PARSE ------------------------------------------ |
|||
# TREE FROM PARSE OF OUTLINE TEXT |
|||
parseTreeFromOutline :: T.Text -> [T.Text] -> Tree Coverage |
|||
fmapTree( |
|||
parseTreeFromOutline delimiter indentedLines = |
|||
recordFromKeysDefaultsDelimiterAndLine(columnTitles)( |
|||
(partialRecord . tokenizeWith delimiter) <$> |
|||
[str, float, float])(['?', 1.0, 0.0])(delimiter) |
|||
head (forestFromLineIndents $ indentLevelsFromLines $ tail indentedLines) |
|||
)( |
|||
forestFromLineIndents(indentLevelsFromLines( |
|||
reportLines[1:] |
|||
))[0] |
|||
) |
|||
) |
|||
) |
|||
)) |
|||
forestFromLineIndents :: [(Int, T.Text)] -> [Tree T.Text] |
|||
forestFromLineIndents pairs = |
|||
let go [] = [] |
|||
go ((n, s):xs) = |
|||
let (firstTreeLines, rest) = span ((n <) . fst) xs |
|||
in Node s (go firstTreeLines) : go rest |
|||
in go pairs |
|||
indentLevelsFromLines :: [T.Text] -> [(Int, T.Text)] |
|||
# WEIGHTED COVERAGE, AND SHARE OF TOTAL RESIDUE ----------- |
|||
indentLevelsFromLines xs = |
|||
let pairs = T.span isSpace <$> xs |
|||
indentUnit = |
|||
foldr |
|||
(\x a -> |
|||
let w = (T.length . fst) x |
|||
in bool a w (w < a && 0 < w)) |
|||
(maxBound :: Int) |
|||
pairs |
|||
in first (flip div indentUnit . T.length) <$> pairs |
|||
partialRecord :: [T.Text] -> Coverage |
|||
# weightedCoverage :: Tree Dict -> |
|||
partialRecord xs = |
|||
# [Tree Dict] -> Tree Dict |
|||
let [name, weightText, coverageText] = take 3 (xs ++ repeat "") |
|||
def weightedCoverage(x): |
|||
in Coverage |
|||
'''The weighted coverage of a tree node, |
|||
{ name = name |
|||
as a function of the weighted averages |
|||
, weight = defaultOrRead 1.0 weightText |
|||
of its children. |
|||
, coverage = defaultOrRead 0.0 coverageText |
|||
''' |
|||
, share = 0.0 |
|||
} |
|||
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) |
|||
defaultOrRead :: Float -> T.Text -> Float |
|||
defaultOrRead n txt = either (const n) fst $ T.rational txt |
|||
tokenizeWith :: T.Text -> T.Text -> [T.Text] |
|||
tokenizeWith delimiter = fmap T.strip . T.splitOn delimiter |
|||
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) |
|||
-- SERIALISATION OF TREE TO TABULATED OUTLINE ------------- |
|||
indentedLinesFromTree :: T.Text -> (T.Text -> a -> T.Text) -> Tree a -> T.Text |
|||
indentedLinesFromTree tab showRoot tree = |
|||
let go indent node = |
|||
showRoot indent (rootLabel node) : |
|||
(subForest node >>= go (T.append tab indent)) |
|||
in T.unlines $ go "" tree |
|||
showCoverage :: T.Text -> Coverage -> T.Text |
|||
# OUTLINE TABULATION -------------------------------------- |
|||
showCoverage indent x = |
|||
tabulation |
|||
([T.append indent (name x), T.pack (showN 0 (weight x))] ++ |
|||
((T.pack . showN 4) <$> ([coverage, share] <*> [x]))) |
|||
tabulation :: [T.Text] -> T.Text |
|||
tabulation = T.intercalate "| " . zipWith (`T.justifyLeft` ' ') [31, 9, 9, 9] |
|||
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 |
|||
)) |
|||
justifyRight :: Int -> a -> [a] -> [a] |
|||
justifyRight n c = (drop . length) <*> (replicate n c ++) |
|||
showN :: Int -> Float -> String |
|||
showN p n = justifyRight 7 ' ' (showFFloat (Just p) n "") |
|||
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 ------------------------------------------------ |
|||
foldTree :: (a -> [b] -> b) -> Tree a -> b |
|||
# GENERIC AND REUSABLE FUNCTIONS -------------------------- |
|||
foldTree f = go |
|||
where |
|||
# Node :: a -> [Tree a] -> Tree a |
|||
go (Node x ts) = f x (map go ts)</lang> |
|||
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}} |
{{Out}} |
||
<pre>NAME_HIERARCHY | WEIGHT | COVERAGE | SHARE OF RESIDUE |
<pre>NAME_HIERARCHY | WEIGHT | COVERAGE | SHARE OF RESIDUE |