Anamorphism

Anamorphism is the one of well known recursive schemes which is defined in pseudocode as:

p :: B -> Bool
g :: B -> A || B
h :: B -> A*
h b = Nil        ,  p b
    = a : h b'   , ¬p b
    where a, b' = g b

The scheme looks like:

p (not shown) is the predicate which "decides" what to return on current step: Nil or to continue to recursion.

It can be easy coded in Python:

def ana(b, g, p):
    if p(b): return []
    else:
        a, b_ = g(b)
        return a + ana(b_, g, p)

Most known example of usage is:

def myzip(l0, l1):
    def g(b):
        x, *xs = b[0]
        y, *ys = b[1]
        if not xs and ys: xs = [None]
        if not ys and xs: ys = [None]
        return ([(x, y)], (xs, ys))
    def p(b):
        return not (b[0] or b[1])
    return ana((l0, l1), g, p)

print(myzip([1,2,3,4], [10,20,30]))
print(list(zip([1,2,3], [10,20,30])))

A specially ZIP looks like:

what is in pseudocode:

zip :: A* || B* -> (A || B)*
zip = ANA<g, p>, where:
  g (a:as, b:bs) = ((a,b), (as, bs))
  p (as, bs) = (as=Nil) | (bs=Nil) -- until one of tails is not empty

Whether it is possible to imagine a parallel form?

Download all files by mime type

Download files of some types from URL:

wget -A ps,djvu -m -p -E -k -K -np -nH -L -l <DEEP> -e robots=off URL

all *.ps, *.djvu will be saved in own directories, but without host folder.

Intervals merge

Two simple algorithms of interval merge, which I designed yesterday while was sick :)

First (and simplest) algorithm

First, is very dumb and is based on check of edges projection: if projected edge (node) is contained in another interval then we have solid interval as result (we must merge them), elsewhere - keep original intervals, see picture:

Python implementation:

# predicat: `x` is contained in (x0, x1)
c = lambda x, x0, x1: x0 <= x <= x1

# merge-I
def m1(i1, i2):
    i1, i2 = map(isort, (i1,i2))
    sx = isort(i1 + i2)
    x1, x2 = i1; x3, x4 = i2
    if c(x1, x3, x4) or c(x3, x1, x2) or c(x2, x3, x4) or c(x4, x1, x2):
        return (sx[0], sx[-1])
    else:
        return ((sx[0], sx[1]), (sx[2], sx[3]))

where isort() is sort function, which returns tuple instead of list:

# sort interval `i`
isort = lambda i: tuple(sorted(i))

Don't forget that first is sort of intervals (normalizing) and then sort of all points - see sx.

Second algorithm

Second is more interesting. It is based on gap detection: we try to find - is there gap between intervals? If it exists then we return 2 intervals as is, otherwise - merge them into one by get (first, last) of sorted points.

where dx is difference between 2nd point of 1st interval - 1st point of 2nd interval (intervals are sorted, so "1st" and "2nd" means index in order), i.e.

D_x = I₁₂ - I₂₁

X_s = {X₁ ≼ X₂ ≼ X₃ ≼ X₄}
I_s = {I₁ ≼ I₂}

I₁₂ - I₂₁ ≥ 0 =>  RESULT := [X₁, X₄]
I₁₂ - I₂₁ < 0     RESULT := [[X₁, X₂], [X₃, X₄]]

where I is interval (pair of 2 X points).

# Tuple 0st item selector
p1 = lambda p: p[0]

# merge-II
def m2(i1, i2):
    i1, i2 = map(isort, (i1,i2))
    sx = isort(i1 + i2)
    si = sorted((i1, i2), key=p1)
    if si[0][1] - si[1][0] >= 0:
        return (sx[0], sx[-1])
    else:
        return ((sx[0], sx[1]), (sx[2], sx[3]))

Test it:

# assert
def ass(a, b):
    if a != b: raise AssertionError('%r != %r' % (a,b))

# asserts algo. m1
ass(((1,2), (10,20)), m1((1,2), (10,20)))
ass(((1,2), (10,20)), m1((2,1), (20,10)))
ass((1,20), m1((2,1), (2,20)))
ass((1,20), m1((10,1), (2,20)))
ass((1,20), m1((20,1), (5,20)))
ass((1,20), m1((20,1), (5,10)))
ass((1,20), m1((20,1), (1,10)))
ass((-1,20), m1((20,1), (-1,10)))
ass((-1,20), m1((20,1), (-1,1)))
ass(((-1,0), (1,20)), m1((20,1), (-1,0)))
ass((1,20), m1((2,10), (20,1)))

ass(((1,2), (10,20)), m2((1,2), (10,20)))
ass(((1,2), (10,20)), m2((2,1), (20,10)))
ass((1,20), m2((2,1), (2,20)))
ass((1,20), m2((10,1), (2,20)))
ass((1,20), m2((20,1), (5,20)))
ass((1,20), m2((20,1), (5,10)))
ass((1,20), m2((20,1), (1,10)))
ass((-1,20), m2((20,1), (-1,10)))
ass((-1,20), m2((20,1), (-1,1)))
ass(((-1,0), (1,20)), m2((20,1), (-1,0)))
ass((1,20), m2((2,10), (20,1)))

print 'ok.'

These algorithms are based on metrics: if we can map nodes to natural numbers, we can apply algorithms to intervals of such nodes, For example, nodes can be cities, and metric will be distance from some center, e.g. capital. This means that it's easy to merge path fragments where path nodes are cities. You can imagine any other case sutisfied such condition.

Expressions notations

What kind of notations for expression syntax do you know? Basincs are:

• INFIX: 5 * 2 + 3 = 13 (implicit precedence)
• POSTFIX: 5 2 * 3 + (stack based, explicit precedence)
• PREFIX: + 3 * 5 2 (reversed postfix)
• NESTED: (+ (* 5 2) 3) (lisp/s-expressions)
• FUNCTIONAL: +( *(5 2) 3) (m-expression)
• MATCHFIX: (* (+ 5 2 +) 3 *) (remembed "end/end if/fi"?)

Another one?

Some of them are very easy for implementation and parsing is trivial (prefix/postfix/nested/matchfix), but more human readable is infix which leads to creation of parsing theory.

Original