fork(1) download
copy 
  1. # Fun with linked-lists. (2.00)
  2.  
  3. class Pair:
  4.     def __init__(self, first=None, rest=None):
  5.         self.first = first
  6.         self.rest = rest
  7.  
  8.     def __repr__(self):
  9.         return '(' + ' '.join(map(str, ltoa(self))) + ')'
  10.  
  11. def atol(a):
  12.     # Array to linked-list.
  13.     r = None
  14.     for x in reversed(a):
  15.         r = Pair(x, r)
  16.     return r
  17.  
  18. def ltoa(l):
  19.     # Linked-list to array.
  20.     return foldl(lambda init, x: init + [x], [], l)
  21.  
  22. def _append(tail, l):
  23.     assert l is None or isinstance(l, Pair), 'Pair expected!'
  24.     # Internal: Copy and append elements.
  25.     while l:
  26.         tail.rest = Pair(l.first)
  27.         tail = tail.rest
  28.         l = l.rest
  29.     return tail
  30.  
  31. def appendl(ls):
  32.     # Append all lists.
  33.     temp = Pair()
  34.     foldl(lambda init, x: _append(init, x), temp, ls)
  35.     return temp.rest
  36.  
  37. def reversel(l):
  38.     # Reverse a list.
  39.     return foldl(lambda init, x: Pair(x, init), None, l)
  40.  
  41. def foldl(proc, init, l):
  42.     # Build result by applying a procedure to list elements.
  43.     return foldlp(lambda init, p: proc(init, p.first), init, l)
  44.  
  45. def foldlp(proc, init, l):
  46.     # Build result by applying a procedure to list pairs.
  47.     while l:
  48.         init = proc(init, l)
  49.         l = l.rest
  50.     return init
  51.  
  52. def foldrightl(proc, init, l):
  53.     # Build result by applying a procedure to list elements last to first.
  54.     return foldrightlp(lambda init, p: proc(init, p.first), init, l)
  55.  
  56. def foldrightlp(proc, init, l):
  57.     # Build result by applying a procedure to list pairs last to first.
  58.     # (Prototypical implementation; limited by maximum recursion depth)
  59.     if not l:
  60.         return init
  61.     return proc(foldrightlp(proc, init, l.rest), l)
  62.  
  63. def foldrightlp(proc, init, l):
  64.     # Build result by applying a procedure to list pairs last to first.
  65.     # (Continuation passing style and trampoline eliminates recursion)
  66.     def cps_detail(l, k):
  67.         if not l:
  68.             return k(init)
  69.         return lambda: cps_detail(l.rest, lambda x: lambda: k(proc(x, l)))
  70.     def trampoline(t):
  71.         while callable(t):
  72.             t = t()
  73.         return t
  74.     return trampoline(cps_detail(l, lambda x: x))
  75.  
  76. def mapl(proc, l):
  77.     # Map procedure over list elements; return list of results.
  78.     return maplp(lambda p: proc(p.first), l)
  79.  
  80. def maplp(proc, l):
  81.     # Map procedure over list pairs; return list of results.
  82.     # (Fold is more efficient than foldright but ...)
  83.     return reversel(foldlp(lambda init, p: Pair(proc(p), init), None, l))
  84.  
  85. def maplp(proc, l):
  86.     # Map procedure over list pairs; return list of results.
  87.     # (... I want to test foldright)
  88.     return foldrightlp(lambda init, p: Pair(proc(p), init), None, l)
  89.  
  90. def appendmapl(proc, l):
  91.     # Map procedure over list elements; return appended results.
  92.     return appendmaplp(lambda p: proc(p.first), l)
  93.  
  94. def appendmaplp(proc, l):
  95.     # Map procedure over list pairs; return appended results.
  96.     return appendl(maplp(proc, l))
  97.  
  98. def combinationsl(l, k):
  99.     # Generate combinations from list.
  100.     if k == 0:
  101.         return Pair()
  102.     return appendmaplp(lambda r: mapl(lambda c: Pair(r.first, c),
  103.                                       combinationsl(r.rest, k-1)), l)
  104.  
  105. # Main.
  106.  
  107. n = 5
  108. l1 = atol(list(range(n)))
  109. l2 = atol(list(range(n, n*2)))
  110. l3 = atol(list(range(n*2, n*3)))
  111.  
  112. print(l1)
  113. print(ltoa(l1))
  114. print(reversel(l1))
  115. print(mapl(lambda x: x**2, l1))
  116. print(appendl(atol([None, l1, None, None, l2, None, None, l3, None])))
  117. print(appendmapl(lambda x: Pair(x), l1))
  118.  
  119. for k in range(n+1):
  120.     print(f'{n} choose {k}')
  121.     print(combinationsl(l1, k))
  122.  
  123. # Time.
  124.  
  125. from time import process_time
  126.  
  127. def _timeit(thunk):
  128.     t = process_time()
  129.     thunk()
  130.     print('Elapsed: {:.6f}s'.format(process_time() - t))
  131.  
  132. def make_f(n, k, count):
  133.     l = atol(list(range(n)))
  134.     def f():
  135.         for _ in range(count):
  136.             combinationsl(l, k)
  137.     return f
  138.  
  139. _timeit(make_f(8, 4, 400))
  140. _timeit(make_f(16, 8, 1))
Success #stdin #stdout 1.56s 23552KB
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 10 11 12 13 14)
(0 1 2 3 4)
5 choose 0
(None)
5 choose 1
((0) (1) (2) (3) (4))
5 choose 2
((0 1) (0 2) (0 3) (0 4) (1 2) (1 3) (1 4) (2 3) (2 4) (3 4))
5 choose 3
((0 1 2) (0 1 3) (0 1 4) (0 2 3) (0 2 4) (0 3 4) (1 2 3) (1 2 4) (1 3 4) (2 3 4))
5 choose 4
((0 1 2 3) (0 1 2 4) (0 1 3 4) (0 2 3 4) (1 2 3 4))
5 choose 5
((0 1 2 3 4))
Elapsed: 0.767655s
Elapsed: 0.689570s
https://ideone.com/aSv0cM
language:
Python 3 (python  3.12)
created:
1 day 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!