Idiomatic backtracking in Python

[Rustom Mody]

On Monday, January 26, 2015 at 12:52:04 PM UTC+5:30, Jussi Piitulainen wrote:
> 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,)).


Sweet


> 
> 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.

Neat 
Thanks