fork download
copy 
  1. # Functional style linked-lists. (2.02)
  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. def _append(tail, l):
  43.     assert l is Pair.NIL or isinstance(l, Pair), 'Pair expected!'
  44.     # @internal
  45.     # Copy and append elements.
  46.     while l:
  47.         tail.rest = Pair(l.first)
  48.         tail = tail.rest
  49.         l = l.rest
  50.     return tail
  51.  
  52. def _reverse(l):
  53.     # @internal
  54.     # Reverse a list (destructive).
  55.     prev = Pair.NIL
  56.     while l:
  57.         rest = l.rest
  58.         l.rest = prev
  59.         prev = l
  60.         l = rest
  61.     return prev
  62.  
  63. # Linked-list.
  64.  
  65. def pairs(*args):
  66.     # Elements to linked-list.
  67.     return pairs_from_iterable(args)
  68.  
  69. def pairs_from_iterable(a):
  70.     # Iterable to linked-list.
  71.     return _reverse(reduce(lambda init, x: Pair(x, init), a, Pair.NIL))
  72.  
  73. def appendl(ls):
  74.     # Append all lists.
  75.     temp = Pair(None)
  76.     foldl(lambda init, x: _append(init, x), temp, ls)
  77.     return temp.rest
  78.  
  79. def reversel(l):
  80.     # Reverse a list.
  81.     return foldl(lambda init, x: Pair(x, init), Pair.NIL, l)
  82.  
  83. def foldl(proc, init, l):
  84.     # Build result by applying a procedure to list elements.
  85.     return foldlp(lambda init, p: proc(init, p.first), init, l)
  86.  
  87. def foldlp(proc, init, l):
  88.     # Build result by applying a procedure to list pairs.
  89.     while l:
  90.         init = proc(init, l)
  91.         l = l.rest
  92.     return init
  93.  
  94. def foldrightl(proc, init, l):
  95.     # Build result by applying a procedure to list elements last to first.
  96.     return foldrightlp(lambda init, p: proc(init, p.first), init, l)
  97.  
  98. def foldrightlp(proc, init, l):
  99.     # Build result by applying a procedure to list pairs last to first.
  100.     return foldl(proc, init, foldlp(lambda init, p: Pair(p, init), Pair.NIL, l))
  101.  
  102. def mapl(proc, l):
  103.     # Map procedure over list elements; return list of results.
  104.     return maplp(lambda p: proc(p.first), l)
  105.  
  106. def maplp(proc, l):
  107.     # Map procedure over list pairs; return list of results.
  108.     return _reverse(foldlp(lambda init, p: Pair(proc(p), init), Pair.NIL, l))
  109.  
  110. def appendmapl(proc, l):
  111.     # Map procedure over list elements; return appended results.
  112.     return appendmaplp(lambda p: proc(p.first), l)
  113.  
  114. def appendmaplp(proc, l):
  115.     # Map procedure over list pairs; return appended results.
  116.     return appendl(maplp(proc, l))
  117.  
  118. def combinationsl(l, k):
  119.     # Generate ordered k-length combinations from list.
  120.     if k == 0:
  121.         return Pair(Pair.NIL)
  122.     return appendmaplp(lambda r: mapl(lambda c: Pair(r.first, c),
  123.                                       combinationsl(r.rest, k-1)), l)
  124.  
  125. # Test.
  126.  
  127. from itertools import combinations
  128.  
  129. n  = 5
  130. l  = pairs_from_iterable(range(n))
  131. l2 = pairs_from_iterable(range(n, n*2))
  132. l3 = pairs_from_iterable('1234')
  133.  
  134. print(l)
  135. print(list(l))
  136. print(reversel(l))
  137. print(mapl(lambda x: x**2, l))
  138. print(appendl(pairs(Pair.NIL, l, Pair.NIL, l2, Pair.NIL)))
  139. print(mapl(lambda x: Pair(x), l))
  140. print(appendmapl(lambda x: Pair(x), l))
  141. print(foldl(lambda x, y: '(' + x + '+' + y + ')', '0', l3))
  142. print(foldrightl(lambda y, x: '(' + x + '+' + y + ')', '0', l3))
  143.  
  144. n = 4
  145. a = range(1, 1+n)
  146. l = pairs_from_iterable(a)
  147.  
  148. def reformat(ls):
  149.     return (tuple(x) for x in ls)
  150.  
  151. for k in range(1+n):
  152.     x = combinationsl(l, k)
  153.     y = list(reformat(x))
  154.     z = list(combinations(a, k))
  155.     print(x)
  156.     assert y == z, f'Mismatch for {n},{k}'
  157. print('Okay.')
  158.  
  159. # Time.
  160.  
  161. from time import process_time
  162.  
  163. def _timeit(thunk):
  164.     try:
  165.         t = process_time()
  166.         thunk()
  167.         print('Elapsed: {:.6f}s'.format(process_time() - t))
  168.     except Exception as e:
  169.         print('Invalid:', e)
  170.  
  171. def make_f(n, k, count):
  172.     l = pairs_from_iterable(range(n))
  173.     def f():
  174.         for _ in range(count):
  175.             combinationsl(l, k)
  176.     return f
  177.  
  178. _timeit(make_f(8, 4, 400))
  179. _timeit(make_f(16, 8, 1))
Success #stdin #stdout 0.92s 23032KB
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.516926s
Elapsed: 0.303451s
https://ideone.com/NRgj1E
language:
Python 3 (python  3.12)
created:
9 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!