fork download
copy 
  1. # Functional style linked-lists. (2.03)
  2. # @see LcJ58j
  3.  
  4. from functools import reduce
  5.  
  6. # Pair.NIL constant.
  7.  
  8. class PairNilType:
  9.     def __bool__(self):
  10.         return False
  11.     def __iter__(self):
  12.         return; yield
  13.     def __repr__(self):
  14.         return '()'
  15.  
  16. class PairBaseProperties(type):
  17.     __nil = PairNilType()
  18.     @property
  19.     def NIL(cls):
  20.         return cls.__nil
  21.  
  22. class PairBase(metaclass=PairBaseProperties):
  23.     pass
  24.  
  25. # Pair.
  26.  
  27. class Pair(PairBase):
  28.     def __init__(self, first, rest=PairBase.NIL):
  29.         self.first = first
  30.         self.rest = rest
  31.  
  32.     def __iter__(self):
  33.         while True:
  34.             yield self.first
  35.             self = self.rest
  36.             if not self:
  37.                 break
  38.  
  39.     def __repr__(self):
  40.         return '(' + ' '.join(map(str, self)) + ')'
  41.  
  42. # Linked-list private.
  43.  
  44. def _append(tail, p):
  45.     # @internal
  46.     # Append list elements; share the last list.
  47.     l = p.first
  48.     assert l is Pair.NIL or isinstance(l, Pair), 'Pair expected!'
  49.     if not p.rest:
  50.         tail.rest = l
  51.     else:
  52.         while l:
  53.             tail.rest = Pair(l.first)
  54.             tail = tail.rest
  55.             l = l.rest
  56.     return tail
  57.  
  58. def _reverse(l):
  59.     # @internal
  60.     # Reverse a list (destructive).
  61.     prev = Pair.NIL
  62.     while l:
  63.         rest = l.rest
  64.         l.rest = prev
  65.         prev = l
  66.         l = rest
  67.     return prev
  68.  
  69. # Linked-list public.
  70.  
  71. def pairs(*args):
  72.     # Elements to linked-list.
  73.     return pairs_from_iterable(args)
  74.  
  75. def pairs_from_iterable(a):
  76.     # Iterable to linked-list.
  77.     return _reverse(reduce(lambda init, x: Pair(x, init), a, Pair.NIL))
  78.  
  79. def appendl(ls):
  80.     # Append all lists.
  81.     temp = Pair(None)
  82.     foldlp(lambda init, p: _append(init, p), temp, ls)
  83.     return temp.rest
  84.  
  85. def reversel(l):
  86.     # Reverse a list.
  87.     return foldl(lambda init, x: Pair(x, init), Pair.NIL, l)
  88.  
  89. def foldl(proc, init, l):
  90.     # Build result by applying a procedure to list elements.
  91.     return foldlp(lambda init, p: proc(init, p.first), init, l)
  92.  
  93. def foldlp(proc, init, l):
  94.     # Build result by applying a procedure to list pairs.
  95.     while l:
  96.         init = proc(init, l)
  97.         l = l.rest
  98.     return init
  99.  
  100. def foldrightl(proc, init, l):
  101.     # Build result by applying a procedure to list elements last to first.
  102.     return foldrightlp(lambda init, p: proc(init, p.first), init, l)
  103.  
  104. def foldrightlp(proc, init, l):
  105.     # Build result by applying a procedure to list pairs last to first.
  106.     return foldl(proc, init, foldlp(lambda init, p: Pair(p, init), Pair.NIL, l))
  107.  
  108. def mapl(proc, l):
  109.     # Map procedure over list elements; return list of results.
  110.     return maplp(lambda p: proc(p.first), l)
  111.  
  112. def maplp(proc, l):
  113.     # Map procedure over list pairs; return list of results.
  114.     return _reverse(foldlp(lambda init, p: Pair(proc(p), init), Pair.NIL, l))
  115.  
  116. def appendmapl(proc, l):
  117.     # Map procedure over list elements; return appended results.
  118.     return appendmaplp(lambda p: proc(p.first), l)
  119.  
  120. def appendmaplp(proc, l):
  121.     # Map procedure over list pairs; return appended results.
  122.     return appendl(maplp(proc, l))
  123.  
  124. def combinationsl(l, k):
  125.     # Generate ordered k-length combinations from list.
  126.     if k == 0:
  127.         return Pair(Pair.NIL)
  128.     return appendmaplp(lambda r: mapl(lambda c: Pair(r.first, c),
  129.                                       combinationsl(r.rest, k-1)), l)
  130.  
  131. # Test.
  132.  
  133. from itertools import combinations
  134.  
  135. n  = 5
  136. l  = pairs_from_iterable(range(n))
  137. l2 = pairs_from_iterable(range(n, n*2))
  138. l3 = pairs_from_iterable('1234')
  139.  
  140. print(l)
  141. print(list(l))
  142. print(reversel(l))
  143. print(mapl(lambda x: x**2, l))
  144. print(appendl(pairs(Pair.NIL, l, Pair.NIL, l2)))
  145. print(mapl(lambda x: Pair(x), l))
  146. print(appendmapl(lambda x: Pair(x), l))
  147. print(foldl(lambda x, y: '(' + x + '+' + y + ')', '0', l3))
  148. print(foldrightl(lambda y, x: '(' + x + '+' + y + ')', '0', l3))
  149.  
  150. n = 4
  151. a = range(1, 1+n)
  152. l = pairs_from_iterable(a)
  153.  
  154. def reformat(ls):
  155.     return (tuple(x) for x in ls)
  156.  
  157. for k in range(1+n):
  158.     x = combinationsl(l, k)
  159.     y = list(reformat(x))
  160.     z = list(combinations(a, k))
  161.     print(x)
  162.     assert y == z, f'Mismatch for {n},{k}'
  163. print('Okay.')
  164.  
  165. # Time.
  166.  
  167. from time import process_time
  168.  
  169. def _timeit(thunk):
  170.     try:
  171.         t = process_time()
  172.         thunk()
  173.         print('Elapsed: {:.6f}s'.format(process_time() - t))
  174.     except Exception as e:
  175.         print('Invalid:', e)
  176.  
  177. def make_f(n, k, count):
  178.     l = pairs_from_iterable(range(n))
  179.     def f():
  180.         for _ in range(count):
  181.             combinationsl(l, k)
  182.     return f
  183.  
  184. _timeit(make_f(8, 4, 400))
  185. _timeit(make_f(16, 8, 1))
Success #stdin #stdout 0.8s 22996KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(0 1 2 3 4)
[0, 1, 2, 3, 4]
(4 3 2 1 0)
(0 1 4 9 16)
(0 1 2 3 4 5 6 7 8 9)
((0) (1) (2) (3) (4))
(0 1 2 3 4)
((((0+1)+2)+3)+4)
(1+(2+(3+(4+0))))
(())
((1) (2) (3) (4))
((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))
((1 2 3) (1 2 4) (1 3 4) (2 3 4))
((1 2 3 4))
Okay.
Elapsed: 0.373870s
Elapsed: 0.323183s
https://ideone.com/TfBrOr
language:
Python 3 (python  3.12)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!