Infinite data structures python

Infinite_data_structures.py

# https://www.onlinegdb.com/online_python_interpreter#

'''
-- immutable, persistent, coinductive streams

ones = 1 : ones

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

hamm = 1 : map (*2) hamm `f` map (*3) hamm `f` map (*5) hamm where
  f xxs@(x:xs) yys@(y:ys) | x==y = x : f xs ys
                          | x<y  = x : f xs yys
                          | x>y  = y : f xxs ys

main = do
  --print $ take 10 ones
  --print $ take 10 fibs
  --print $ take 10 hamm
'''

############################ FINITE LISTS ############################

######################################################################
# CONS / CAR / CDR
######################################################################

# 1-st variant
def cons(x, y): return x, y
def car(l):     return l[0]
def cdr(l):     return l[1]

'''

# 2-nd variant
class ConsList:
    def __init__(self, x, y): self.car, self.cdr = x, y

def cons(x, y): return ConsList(x, y)
def car(l):     return l.car
def cdr(l):     return l.cdr


# 3-rd variant
def cons(x, y): return lambda f: f(x, y)
def car(l):     return l(lambda x, y: x)
def cdr(l):     return l(lambda x, y: y)


# 4-th variant
def cons(x, y): return lambda c: x if (c == 0) else y
def car(l):     return l(0)
def cdr(l):     return l(1)

'''

######################################################################
# SERVICE FUNCTIONS & HELPERS
######################################################################

nil = cons(None, None)

def isnull(l): return car(l) is None and cdr(l) is None

def l(*args): return cons(args[0], l(*args[1:])) if args else nil

def vec(l):
  r = []
  while not isnull(l):
    r.append(car(l))
    l = cdr(l)
  return r

def show(l):  
  try:
    r = ''
    while not isnull(l):
      r = r + ' ' + show(car(l))
      l = cdr(l)
    return '(' + r[1:] + ')'
  except Exception as ex:
    return str(l)

#a = l()
#a = l(1)
#a = l(1, 2)
#a = l(1, l(2, 3), l(4, l(5, 6, l(7), 8), 9), 10)
#print("RAW ", a)
#print("SHOW", show(a))

######################################################################
# STANDARD LIBRARY LIST FUNCTIONS - MAP, FILTER, REDUCE
######################################################################

'''
def foldl(f, a, l):
  if isnull(l):
    return a
  else:
    return foldl(f, f(car(l), a), cdr(l))
'''
def foldl(f, a, l):
  r = a
  while not isnull(l):
    r = f(car(l), r)
    l = cdr(l)
  return r

def foldr(f, a, l):
  if isnull(l):
    return a
  else:
    return f(car(l), foldr(f, a, cdr(l)))

def reverse(l): return foldl(cons, nil, l)

'''
def map(f, l):
  if isnull(l):
    return nil
  else:
    return cons(f(car(l)), map(f, cdr(l)))
'''
def mapReverse(f, l):
  r = nil
  while not isnull(l):
    r = cons(f(car(l)), r)
    l = cdr(l)
  return r

def map(f, l): return reverse(mapReverse(f, l))

'''
def filter(f, l):
  if isnull(l):
    return nil
  elif f(car(l)):
    return cons(car(l), filter(f, cdr(l)))
  else:
    return filter(f, cdr(l))
'''
def filterReverse(f, l):
  r = nil
  while not isnull(l):
    x = car(l)
    r = cons(x, r) if f(x) else r
    l = cdr(l)
  return r

def filter(f, l): return reverse(filterReverse(f, l))

def listFromTo(a, b): return nil if (a>b) else  cons(a, listFromTo(a+1, b))

'''
a = listFromTo(1, 10)

print("RAW        ", a)
print("SHOW       ", show(a))
print("MAP (*10)  ", show(map(lambda x: x*10, a)))
print("FILTER EVEN", show(filter(lambda x: x%2 == 0, a)))
print("REVERSE    ", show(reverse(a)))
print("LEFT  FOLD ", foldl(lambda x, y: str(x) + '-' + str(y), '>', a))
print("RIGHT FOLD ", foldr(lambda x, y: str(x) + '-' + str(y), '>', a))
print("SUM FOLDL  ", foldl(lambda x, y: x+y, 0, a))
print("SUM FOLDR  ", foldr(lambda x, y: x+y, 0, a))
'''

######################################################################
# EXAMPLE TASK - KNIGHT ROUTE
######################################################################

def cadr(l): return car(cdr(l))

'''
def eq(a, b):
  if isnull(a): return isnull(b)
  elif isnull(b): return isnull(a)
  else: return car(a) == car(b) and eq(cdr(a), cdr(b))
'''
def eq(a, b):
  while not isnull(a) or not isnull(b):
    if isnull(a): return isnull(b)
    elif isnull(b): return isnull(a)
    elif car(a) != car(b): return False
    a = cdr(a)
    b = cdr(b)
  return True

'''
def existStep(a, b, c):
  if isnull(cdr(c)): return False
  elif eq(a, car(c)) and eq(b, cadr(c)): return True
  else: return existStep(a, b, cdr(c))
'''
def existStep(a, b, c):
  while not isnull(cdr(c)):
    if eq(a, car(c)) and eq(b, cadr(c)): return True
    c = cdr(c)
  return False

steps = l(l(2,1), l(1,2), l(-1,2), l(-2,1), l(-2,-1), l(-1,-2), l(1,-2), l(2,-1))

def nextPos(c, m, n):
  p = car(c)
  s = filter(lambda x: (1 <= car(x) <= m and 1 <= cadr(x) <= n),
             map(lambda x: l(car(p) + car(x), cadr(p) + cadr(x)), steps))
  return filter(lambda x: not existStep(x, p, c), s)

def nextChains(c, m, n): return map(lambda x: cons(x, c), nextPos(c, m, n))

'''
def elem(x, l):
  if isnull(l): return False
  elif eq(x, car(l)): return True
  else: return elem(x, cdr(l))
'''
def elem(x, l):
  while not isnull(l):
    if eq(x, car(l)): return True
    l = cdr(l)
  return False
    
def isFullChain(c, m, n, field): return eq(car(c), l(1,1)) and isnull(filter(lambda x: not elem(x, c), field))

def knightCore(c, m, n, field):
  nc = nextChains(c, m, n)
  if isFullChain(c, m, n, field): return c
  elif isnull(nc): return nil
  else: return foldl(lambda x, a: knightCore(x, m, n, field) if isnull(a) else a, nil, nc)

def knight(m, n):
  field = foldl(lambda x, b: foldl(lambda y, a: cons(l(x, y), a), b, listFromTo(1, n)), nil, listFromTo(1, m))
  return knightCore(l(l(1,1)), m, n, field)

#print("KNIGHT ROUTE", show(knight(7, 7)))
#print("KNIGHT ROUTE", show(knight(7, 9)))










########################### INFINITE LISTS ###########################

######################################################################
# CONS / CAR / CDR
######################################################################

# 1-st variant
def cons(x, y): return x, y
def car(l):     return l[0]
def cdr(l):     return l[1]

'''
# 2-nd variant
class ConsList:
    def __init__(self, x, y): self.car, self.cdr = x, y

def cons(x, y): return ConsList(x, y)
def car(l):     return l.car
def cdr(l):     return l.cdr


# 3-rd variant
def cons(x, y): return lambda f: f(x, y)
def car(l):     return l(lambda x, y: x)
def cdr(l):     return l(lambda x, y: y)


# 4-th variant
def cons(x, y): return lambda c: x if (c == 0) else y
def car(l):     return l(0)
def cdr(l):     return l(1)
'''

######################################################################
# SERVICE FUNCTIONS & HELPERS
######################################################################

# scons(h, t) = cons(h, lz(lambda: t))


# 1-st variant
def lz(x): return x

def stail(s):
  t = cdr(s) 
  return t() if callable(t) else t

'''
# 2-nd variant
def lz(x): return Lazy(x)

def stail(s):
  t = cdr(s) 
  return t.getvalue() if isinstance(t, Lazy) else t

class Lazy:
  def __init__(self, expr):
    self.expression = expr
  
  def getvalue(self): return self.expression()


# 3-rd variant
def lz(x): return Lazy(x)

def stail(s):
  t = cdr(s) 
  return t.getvalue() if isinstance(t, Lazy) else t

class Lazy:
  def __init__(self, expr):
    self.expression = expr
    self.calculated = False
    self.rezult = False
  
  def getvalue(self):
    if not self.calculated:
      self.rezult = self.expression()
      self.calculated = True
    return self.rezult
'''


def stake(n, s):
  r = []
  while n > 0:
    r.append(car(s))
    s = stail(s)
    n = n-1
  return r

def snth(n, s):
  while n > 0:
    s = stail(s)
    n = n-1
  return car(s)

######################################################################
# STANDARD LIBRARY STREAM FUNCTIONS - MAP, FILTER
######################################################################

def smap(f, s): return cons(f(car(s)), lz(lambda: smap(f, stail(s))))

def sfilter(f, s): return cons(car(s), lz(lambda: sfilter(f, stail(s)))) if f(car(s)) else sfilter(f, stail(s))

######################################################################
# SIMPLE EXAMPLES
######################################################################

ones = cons(1, lz(lambda: ones))
#print("RAW ", ones)
#print("ONES", stake(10, ones))

#-----------------------

def intfrom(n): return cons(n, lz(lambda: intfrom(n+1)))
#print("NATS ", stake(10, intfrom(1)))

#-----------------------

def partialsums (s):
  def go(a, s): return cons(a+car(s), lz(lambda: go(a+car(s), stail(s))))
  return go(0, s)
#print("PART SUMS", stake(50, partialsums(intfrom(1))))

#-----------------------

streamOfStreams = smap(intfrom, intfrom(0))
#print("STREAM OF STREAMS", stake(10, smap(lambda s: stake(5, s), streamOfStreams)))

#-----------------------

evens = sfilter(lambda x: x%2 == 0, intfrom(0))
#print("EVENS", stake(10, evens))

#-----------------------

def ssum(a, b): return cons(car(a)+car(b), lz(lambda: ssum(stail(a), stail(b))))

fibs = cons(0, cons(1, lz(lambda: ssum(stail(fibs), fibs))))
#print("FIBS EXP", stake(10, fibs))
#print("FIBS EXP", stake(25, fibs))

def fibgen(a, b): return cons(a, lz(lambda: fibgen(b, a+b)))
fibsLin = fibgen(0, 1)
#print("FIBS LIN", stake(100, fibsLin))

#-----------------------

def sk (k, s): return smap(lambda x: k*x, s)

def merge(a, b):
  if   car(a) < car(b): return cons(car(a), lz(lambda: merge(stail(a), b)))
  elif car(a) > car(b): return cons(car(b), lz(lambda: merge(a, stail(b))))
  else:                 return cons(car(a), lz(lambda: merge(stail(a), stail(b))))

hamm = cons(1, lz(lambda: merge(sk(2,hamm), merge(sk(3,hamm), sk(5,hamm)))))
#print("HAMMING NUMBERS", stake(50, hamm))

#-----------------------

def sieve(s):
  r = sfilter(lambda x: x % car(s) != 0, stail(s))
  return cons(car(s), lz(lambda: sieve(r)))
primesErat = sieve(intfrom(2))
#print("PRIMES ERAT", stake(50, primesErat))

#-----------------------

intfrom3 = intfrom(3)
primesBert = cons(2, lz(lambda: sfilter(isprime, intfrom3)))
'''
def isprime(n):
  def iter(s):
    if car(s)*car(s) > n: return True
    elif n % car(s) == 0: return False
    else: return iter(stail(s))
  return iter(primesBert)
'''
def isprime(n):
  s = primesBert
  while car(s) * car(s) <= n:
    if n % car(s) == 0: return False
    s = stail(s)
  return True
#print("PRIMES BERT", stake(50, primesBert))
#print("N-TH PRIME", snth(10000, primesBert))