fork download
copy 
  1. # Functional style linked-lists. (2.01)
  2.  
  3. from functools import reduce
  4.  
  5. class Pair:
  6.     def __init__(self, first=None, rest=None):
  7.         self.first = first
  8.         self.rest = rest
  9.  
  10.     def __repr__(self):
  11.         return '(' + ' '.join(map(str, ltoa(self))) + ')'
  12.  
  13. def _append(tail, l):
  14.     assert l is None or isinstance(l, Pair), 'Pair expected!'
  15.     # @internal
  16.     # Copy and append elements.
  17.     while l:
  18.         tail.rest = Pair(l.first)
  19.         tail = tail.rest
  20.         l = l.rest
  21.     return tail
  22.  
  23. def _reverse(l):
  24.     # @internal
  25.     # Reverse a list (destructive).
  26.     prev = None
  27.     while l:
  28.         rest = l.rest
  29.         l.rest = prev
  30.         prev = l
  31.         l = rest
  32.     return prev
  33.  
  34. def atol(a):
  35.     # Iterable to linked-list.
  36.     return _reverse(reduce(lambda init, x: Pair(x, init), a, None))
  37.  
  38. def ltoa(l):
  39.     # Linked-list to array.
  40.     return foldl(lambda init, x: init + [x], [], l)
  41.  
  42. def appendl(ls):
  43.     # Append all lists.
  44.     temp = Pair()
  45.     foldl(lambda init, x: _append(init, x), temp, ls)
  46.     return temp.rest
  47.  
  48. def reversel(l):
  49.     # Reverse a list.
  50.     return foldl(lambda init, x: Pair(x, init), None, l)
  51.  
  52. def foldl(proc, init, l):
  53.     # Build result by applying a procedure to list elements.
  54.     return foldlp(lambda init, p: proc(init, p.first), init, l)
  55.  
  56. def foldlp(proc, init, l):
  57.     # Build result by applying a procedure to list pairs.
  58.     while l:
  59.         init = proc(init, l)
  60.         l = l.rest
  61.     return init
  62.  
  63. def foldrightl(proc, init, l):
  64.     # Build result by applying a procedure to list elements last to first.
  65.     return foldrightlp(lambda init, p: proc(init, p.first), init, l)
  66.  
  67. def foldrightlp(proc, init, l):
  68.     # Build result by applying a procedure to list pairs last to first.
  69.     # (Prototypical implementation; limited by maximum recursion depth)
  70.     if not l:
  71.         return init
  72.     return proc(foldrightlp(proc, init, l.rest), l)
  73.  
  74. def foldrightlp(proc, init, l):
  75.     # Build result by applying a procedure to list pairs last to first.
  76.     # (Continuation passing style and trampoline eliminates recursion;
  77.     # precludes callable result)
  78.     def cps_detail(l, k):
  79.         if not l:
  80.             return k(init)
  81.         return lambda: cps_detail(l.rest, lambda x: lambda: k(proc(x, l)))
  82.     def trampoline(t):
  83.         while callable(t):
  84.             t = t()
  85.         return t
  86.     return trampoline(cps_detail(l, lambda x: x))
  87.  
  88. def foldrightlp(proc, init, l):
  89.     # Build result by applying a procedure to list pairs last to first.
  90.     # (Fold over reversed list of pairs; requires temporary list)
  91.     return foldl(proc, init, foldlp(lambda init, p: Pair(p, init), None, l))
  92.  
  93. def mapl(proc, l):
  94.     # Map procedure over list elements; return list of results.
  95.     return maplp(lambda p: proc(p.first), l)
  96.  
  97. def maplp(proc, l):
  98.     # Map procedure over list pairs; return list of results.
  99.     # (Fold is more efficient than foldright but ...)
  100.     return _reverse(foldlp(lambda init, p: Pair(proc(p), init), None, l))
  101.  
  102. def maplp(proc, l):
  103.     # Map procedure over list pairs; return list of results.
  104.     # (... I want to test foldright)
  105.     return foldrightlp(lambda init, p: Pair(proc(p), init), None, l)
  106.  
  107. def appendmapl(proc, l):
  108.     # Map procedure over list elements; return appended results.
  109.     return appendmaplp(lambda p: proc(p.first), l)
  110.  
  111. def appendmaplp(proc, l):
  112.     # Map procedure over list pairs; return appended results.
  113.     return appendl(maplp(proc, l))
  114.  
  115. def combinationsl(l, k):
  116.     # Generate ordered k-length combinations from list.
  117.     if k == 0:
  118.         return Pair()
  119.     return appendmaplp(lambda r: mapl(lambda c: Pair(r.first, c),
  120.                                       combinationsl(r.rest, k-1)), l)
  121.  
  122. # Test.
  123.  
  124. from itertools import combinations
  125.  
  126. n = 5
  127. l = atol(range(n))
  128. l2 = atol(range(n, n*2))
  129. print(l)
  130. print(ltoa(l))
  131. print(reversel(l))
  132. print(mapl(lambda x: x**2, l))
  133. print(appendl(atol([None, l, None, None, l2, None])))
  134. print(mapl(lambda x: Pair(x), l))
  135. print(appendmapl(lambda x: Pair(x), l))
  136.  
  137. def reformat(ls):
  138.     return (tuple(ltoa(x)) for x in ltoa(ls))
  139.  
  140. n = 4
  141. a = range(1, 1+n)
  142. l = atol(a)
  143. for k in range(1+n):
  144.     x = list(reformat(combinationsl(l, k)))
  145.     y = list(combinations(a, k))
  146.     print(x)
  147.     print(y)
  148.     assert x == y, f'Mismatch for {n},{k}'
  149. print('Okay.')
  150.  
  151. # Time.
  152.  
  153. from time import process_time
  154.  
  155. def _timeit(thunk):
  156.     try:
  157.         t = process_time()
  158.         thunk()
  159.         print('Elapsed: {:.6f}s'.format(process_time() - t))
  160.     except Exception as e:
  161.         print('Invalid:', e)
  162.  
  163. def make_f(n, k, count):
  164.     l = atol(range(n))
  165.     def f():
  166.         for _ in range(count):
  167.             combinationsl(l, k)
  168.     return f
  169.  
  170. _timeit(make_f(8, 4, 475))
  171. _timeit(make_f(16, 8, 1))
Success #stdin #stdout 1.1s 23028KB
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)
[()]
[()]
[(1,), (2,), (3,), (4,)]
[(1,), (2,), (3,), (4,)]
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (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), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
[(1, 2, 3, 4)]
[(1, 2, 3, 4)]
Okay.
Elapsed: 0.572445s
Elapsed: 0.426379s
https://ideone.com/LcJ58j
language:
Python 3 (python  3.12)
created:
10 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!