Sort an outline at every level: Difference between revisions

=={{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>