Idiomatic backtracking in Python
Jussi Piitulainen
jpiitula at ling.helsinki.fi
Mon Jan 26 02:21:53 EST 2015
Rustom Mody writes:
> To add to Ian:
>
> The classic way of doing it in a functional framework is called:
> "Replace failure by list of successes"
>
> https://rkrishnan.org/files/wadler-1985.pdf
>
> The things that have to go into it are
> 1. Extensive use of list comprehensions
> 2. Lazy lists
>
> Just change in the above 'list' to 'generator'
> and more or less it should work in python
>
> More or less that means when you have a comprehension
> [expr for x in list2 for y in list2 etc]
>
> change the '[]' to '()'
> and recursively change the list1 list2 to gen1 gen2
>
> Some nuisances that bug me (or I dont know how to handle):
>
> 1. Singleton
> [val] becomes (x for x in [val]) (Hoo Boy!)
>
> Or
> def single_val(): yield val
It's just one def:
def sing(*args):
for arg in args:
yield arg
Or not even that: iter((val,)).
But see below at the end.
> 2. Nice syntax like list +
>
> Compare [1] + [2]
> with
>
> >>> from itertools import chain
> >>> a = (x for x in [1])
> >>> b = (x for x in [2])
> >>> list(chain(a,b))
> [1, 2]
>
> Of course it looks worse because the (syntax) overhead of jumping
> between lists and generators overwhelms in this trivial case
Yes, one wouldn't jump back and forth so much. Just collect the result
at the end.
>>> list(chain(sing(3,1,4), sing(1), sing(5,9,2,6)))
[3, 1, 4, 1, 5, 9, 2, 6]
>>> list(chain(sing(3,1,4,1), sing(), sing(5,9,2,6)))
[3, 1, 4, 1, 5, 9, 2, 6]
And it gets better: chain takes lists! And tuples! For those who like
their brackets round:
>>> tuple(chain((3,1,4,1), (), (5,9,2,6)))
(3, 1, 4, 1, 5, 9, 2, 6)
>>> set(chain((3,)))
{3}
>>> list(chain(()))
[]
So chain does it all.
More information about the Python-list
mailing list