Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #84591

Re: Idiomatic backtracking in Python

Show all headers | View raw

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.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Idiomatic backtracking in Python Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-01-25 21:15 +0100
  Re: Idiomatic backtracking in Python Ian Foote <ian@feete.org> - 2015-01-25 20:51 +0000
    Re: Idiomatic backtracking in Python Rustom Mody <rustompmody@gmail.com> - 2015-01-25 18:41 -0800
      Re: Idiomatic backtracking in Python Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2015-01-26 09:21 +0200
        Re: Idiomatic backtracking in Python Rustom Mody <rustompmody@gmail.com> - 2015-01-25 23:28 -0800
  Re: Idiomatic backtracking in Python Ben Finney <ben+python@benfinney.id.au> - 2015-01-26 11:32 +1100
    Re: Idiomatic backtracking in Python Marko Rauhamaa <marko@pacujo.net> - 2015-01-26 03:31 +0200
      Re: Idiomatic backtracking in Python Chris Angelico <rosuav@gmail.com> - 2015-01-26 12:45 +1100
      Re: Idiomatic backtracking in Python Dave Angel <davea@davea.name> - 2015-02-03 16:16 -0500
      Re: Idiomatic backtracking in Python Chris Angelico <rosuav@gmail.com> - 2015-02-04 09:29 +1100
  Re: Idiomatic backtracking in Python MRAB <python@mrabarnett.plus.com> - 2015-01-26 00:43 +0000
  Re: Idiomatic backtracking in Python Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-01-26 08:06 +0000
  Re: Idiomatic backtracking in Python sjmsoft@gmail.com - 2015-01-27 04:48 -0800

csiph-web