Sort an outline at every level: Difference between revisions
→{{header|Python}}: Added a first draft in Python.
m (→{{header|Phix}}: crash->msg) |
(→{{header|Python}}: Added a first draft in Python.) |
||
Line 1,066:
**inconsistent indent** (gamma, line 3)
</pre>
=={{header|Python}}==
<lang python>'''Sort an outline at every level'''
from itertools import chain, product, takewhile, tee
from functools import cmp_to_key, reduce
# ------------- OUTLINE SORTED AT EVERY LEVEL --------------
# sortedOutline :: (Tree String -> Tree String -> Ordering)
# -> String
# -> Either String String
def sortedOutline(cmp):
'''Either a message reporting inconsistent
indentation, or an outline sorted at every
level by the supplied comparator function.
'''
def go(outlineText):
indentTuples = indentTextPairs(
outlineText.splitlines()
)
return bindLR(
minimumIndent(enumerate(indentTuples))
)(lambda unitIndent: Right(
outlineFromForest(
unitIndent,
nest(foldTree(
lambda x: lambda xs: Node(x)(
sorted(xs, key=cmp_to_key(cmp))
)
)(Node('')(
forestFromIndentLevels(
indentLevelsFromLines(
unitIndent
)(indentTuples)
)
)))
)
))
return go
# -------------------------- TEST --------------------------
# main :: IO ()
def main():
'''Ascending and descending sorts attempted on
space-indented and tab-indented outlines, both
well-formed and ill-formed.
'''
ascending = comparing(root)
descending = flip(ascending)
spacedOutline = '''
zeta
beta
gamma
lambda
kappa
mu
delta
alpha
theta
iota
epsilon'''
tabbedOutline = '''
zeta
beta
gamma
lambda
kappa
mu
delta
alpha
theta
iota
epsilon'''
confusedOutline = '''
alpha
epsilon
iota
theta
zeta
beta
delta
gamma
kappa
lambda
mu'''
raggedOutline = '''
zeta
beta
gamma
lambda
kappa
mu
delta
alpha
theta
iota
epsilon'''
def testSort(cmp, cmpName, outlineName):
'''Print either message or result.
'''
def go(outline):
print('\n' + outlineName, cmpName + ':')
either(print)(print)(
sortedOutline(cmp)(outline)
)
return go
def displaySort(kcmp):
k, cmp = kcmp
return [
testSort(cmp, k, label)(
outline
) for (label, outline) in [
('4-space indented', spacedOutline),
('tab indented', tabbedOutline),
('Unknown 1', confusedOutline),
('Unknown 2', raggedOutline)
]
]
# Tests applied to two comparators:
ap([
displaySort
])([
("(A -> Z)", ascending),
("(Z -> A)", descending)
])
# ------------- OUTLINE PARSING AND RENDERING --------------
# forestFromIndentLevels :: [(Int, a)] -> [Tree a]
def forestFromIndentLevels(tuples):
'''A list of trees derived from a list of values paired
with integers giving their levels of indentation.
'''
def go(xs):
if xs:
intIndent, v = xs[0]
firstTreeLines, rest = span(
lambda x: intIndent < x[0]
)(xs[1:])
return [Node(v)(go(firstTreeLines))] + go(rest)
else:
return []
return go(tuples)
# indentLevelsFromLines :: String -> [(String, String)]
# -> [(Int, String)]
def indentLevelsFromLines(indentUnit):
'''Each input line stripped of leading
white space, and tupled with a preceding integer
giving its level of indentation from 0 upwards.
'''
def go(xs):
w = len(indentUnit)
return [
(len(x[0]) // w, x[1])
for x in xs
]
return go
# indentTextPairs :: [String] -> (String, String)
def indentTextPairs(xs):
'''A list of (indent, bodyText) pairs.'''
def indentAndText(s):
pfx = list(takewhile(lambda c: c.isspace(), s))
return (pfx, s[len(pfx):])
return [indentAndText(x) for x in xs]
# outlineFromForest :: String -> [Tree String] -> String
def outlineFromForest(tabString, forest):
'''An indented outline serialisation of forest,
using tabString as the unit of indentation.
'''
def go(indent):
def serial(node):
return [indent + root(node)] + list(
concatMap(
go(tabString + indent)
)(nest(node))
)
return serial
return '\n'.join(
concatMap(go(''))(forest)
)
# --------------- MINIMUM INDENT, OR ANOMALY ---------------
# minimumIndent :: [(Int, [Char])]
# -> Either String String
def minimumIndent(indexedPrefixes):
'''Either a message, if indentation characters are
mixed, or indentation widths are inconsistent,
or the smallest consistent non-empty indentation.
'''
(xs, ts) = tee(indexedPrefixes)
(ys, zs) = tee(ts)
def mindentLR(charSet):
if list(charSet):
def w(x):
return len(x[1][0])
unit = min(filter(w, ys), key=w)[1][0]
unitWidth = len(unit)
def widthCheck(a, ix):
'''Is there a line number at which
an anomalous indent width is seen?
'''
wx = len(ix[1][0])
return a if (a or 0 == wx) else (
ix[0] if 0 != wx % unitWidth else a
)
oddLine = reduce(widthCheck, zs, None)
return Left(
'Inconsistent indentation width at line ' + (
str(1 + oddLine)
)
) if oddLine else Right(''.join(unit))
else:
return Right('')
def tabSpaceCheck(a, ics):
'''Is there a line number at which a
variant indent character is used?
'''
charSet = a[0].union(set(ics[1][0]))
return a if a[1] else (
charSet, ics[0] if 1 < len(charSet) else None
)
indentCharSet, mbAnomalyLine = reduce(
tabSpaceCheck, xs, (set([]), None)
)
return bindLR(
Left(
'Mixed indent characters found in line ' + str(
1 + mbAnomalyLine
)
) if mbAnomalyLine else Right(list(indentCharSet))
)(mindentLR)
# ------------------------ GENERIC -------------------------
# Left :: a -> Either a b
def Left(x):
'''Constructor for an empty Either (option type) value
with an associated string.
'''
return {'type': 'Either', 'Right': None, 'Left': x}
# Right :: b -> Either a b
def Right(x):
'''Constructor for a populated Either (option type) value'''
return {'type': 'Either', 'Left': None, 'Right': x}
# 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}
# ap (<*>) :: [(a -> b)] -> [a] -> [b]
def ap(fs):
'''The application of each of a list of functions,
to each of a list of values.
'''
def go(xs):
return [
f(x) for (f, x)
in product(fs, xs)
]
return go
# bindLR (>>=) :: Either a -> (a -> Either b) -> Either b
def bindLR(m):
'''Either monad injection operator.
Two computations sequentially composed,
with any value produced by the first
passed as an argument to the second.
'''
def go(mf):
return (
mf(m.get('Right')) if None is m.get('Left') else m
)
return go
# comparing :: (a -> b) -> (a -> a -> Ordering)
def comparing(f):
'''An ordering function based on
a property accessor f.
'''
def go(x, y):
fx = f(x)
fy = f(y)
return -1 if fx < fy else (1 if fx > fy else 0)
return go
# concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
'''A concatenated list over which a function has been mapped.
The list monad can be derived by using a function f which
wraps its output in a list,
(using an empty list to represent computational failure).
'''
def go(xs):
return chain.from_iterable(map(f, xs))
return go
# either :: (a -> c) -> (b -> c) -> Either a b -> c
def either(fl):
'''The application of fl to e if e is a Left value,
or the application of fr to e if e is a Right value.
'''
return lambda fr: lambda e: fl(e['Left']) if (
None is e['Right']
) else fr(e['Right'])
# flip :: (a -> b -> c) -> b -> a -> c
def flip(f):
'''The binary function f with its
arguments reversed.
'''
return lambda a, b: f(b, a)
# foldTree :: (a -> [b] -> b) -> Tree a -> b
def foldTree(f):
'''The catamorphism on trees. A summary
value defined by a depth-first fold.
'''
def go(node):
return f(root(node))([
go(x) for x in nest(node)
])
return go
# nest :: Tree a -> [Tree a]
def nest(t):
'''Accessor function for children of tree node.'''
return t.get('nest')
# root :: Tree a -> a
def root(t):
'''Accessor function for data of tree node.'''
return t.get('root')
# 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 match(ab):
b = ab[1]
return not b or not p(b[0])
def f(ab):
a, b = ab
return a + [b[0]], b[1:]
def go(xs):
return until(match)(f)(([], xs))
return go
# 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):
def g(x):
v = x
while not p(v):
v = f(v)
return v
return g
return go
# MAIN ---
if __name__ == '__main__':
main()</lang>
{{Out}}
<pre>4-space indented (A -> Z):
alpha
epsilon
iota
theta
zeta
beta
delta
gamma
kappa
lambda
mu
tab indented (A -> Z):
alpha
epsilon
iota
theta
zeta
beta
delta
gamma
kappa
lambda
mu
Unknown 1 (A -> Z):
Mixed indent characters found in line 4
Unknown 2 (A -> Z):
Inconsistent indentation width at line 3
4-space indented (Z -> A):
zeta
gamma
mu
lambda
kappa
delta
beta
alpha
theta
iota
epsilon
tab indented (Z -> A):
zeta
gamma
mu
lambda
kappa
delta
beta
alpha
theta
iota
epsilon
Unknown 1 (Z -> A):
Mixed indent characters found in line 4
Unknown 2 (Z -> A):
Inconsistent indentation width at line 3</pre>
=={{header|Wren}}==
| |||