Програмиране с Python

Безкрайни списъци

Привет!

Някой дали знае как мога да получа сечението на 2 (или 3, или 5) безкрайни списъка и да взема първите 3 (или 20) елемента от тях, ест., мързеливо, без да се изчислява всичко. Хрумна ми, че в Haskell това е вградено в езика, но при Пайтън няма нищо от рода на range(1,) или range(1..). Освен това създаването на безкраен генератор (чрез generator-expression или дефиниране на функцийка) не е голяма философия, но вземането на списък не е 'мързеливо' и не можем да направим list(fibs())[:10] и да дочакаме резултата.

Прочетох пак 9та лекция, но не ме осени прозрение.

Ще ми се, примерно, да си дефинирам 'всички' прости и 'всички' фибоначи и да взема първите няколко, които са в сечението. Работата е там, че не искам да слагам горна граница, както е в повечето примери от слайдовете.

09.08.2009

Зорница Костадинова
Аналога на безкрайни списъци в Пайтън са генераторите. Няма проблем да си напишеш range, който връща естествените числа например, или Python аналозите на drop и take от Haskell. Проблема е, че повечето вградени функции в Пайтън предполагат, че генераторите ще са крайни и трябва да си напишеш свои lazy версии.

От друга страна, ако искаш да използваш подобен стил програмиране, по-добре направо пиши на Haskell. =-)

Btw, може би Polyglot Quine е по-добро място където да задаваш въпроси от тоя род.

10.08.2009

Славомир Къслев
Ето прост пример за работа с "безкрайни списъци" в Пайтън:
```
def enum(start):
    i = start
    while True:
        yield i
        i += 1

def take(n, xs):
    for i,x in enumerate(xs):
        if i >= n:
            break
        yield x

def drop(n, xs):
    for i,x in enumerate(xs):
        if i < n:
            continue
        yield x
```
```
>>> list(take(10, enum(0)))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list(take(10, drop(10, enum(0))))
[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
```
В Пайтън списъците са винаги крайни, само генераторите могат да бъдат безкрайни. Така, основната идея е, че работиш с генератори и накрая, когато си получила нещо крайно го обръщаш в списък.

10.08.2009
Славомир Къслев

Ето и разширена версия:

def enum(start):
    i = start
    while True:
        yield i
        i += 1

def take(n, xs):
    for i,x in enumerate(xs):
        if i >= n:
            break
        yield x

def drop(n, xs):
    for i,x in enumerate(xs):
        if i < n:
            continue
        yield x

def takeWhile(f, xs):
    for x in xs:
        if not f(x):
            break
        yield x

def dropWhile(f, xs):
    for x in xs:
        if not f(x):
            yield x
            break
    for x in xs:
        yield x

def primes():
    yield 2
    for x in enum(3):
        if all(x % p != 0 for p in takeWhile(lambda p: p**2 <= x, primes())):
            yield x

def fibs():
    a,b = 0,1
    while True:
        yield a
        a,b = a+b,a

def same(xs, ys):
    x,y = next(xs),next(ys)
    while True:
        if x == y:
            yield x
            x,y = next(xs),next(ys)
        elif x < y:
            x = next(xs)
        else:
            y = next(ys)

>>> list(take(6, same(fibs(), primes())))
[2, 3, 5, 13, 89, 233]

Само не пробвай list(take(6, same(fibs(), primes()))), че аз така и не дочаках да видя кое е 6-тото просто число на Фибоначи. =-)

Haskell кода би бил много по-елегантен...

Edit: Поправих малко кода (имаше бъг в dropWhile) и оптимизирах primes, така че вече може да смята 6-тото просто Фибоначи доста бързо.

10.08.2009 (променeно 19.08.2009)

Славомир Къслев

Задължителната Haskell версия:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
primes = 2 : filter isPrime [3..] where
    isPrime x = and [x `mod` p /= 0 | p <- takeWhile (\p -> p^2 <= x) primes]
same xxs@(x:xs) yys@(y:ys)
    | x == y    = x : same xs ys
    | x <  y    = same xs yys
    | otherwise = same xxs ys

която дори може да сметне бързо 8-то просто Фибоначи:

*Main> take 7 (same fibs primes)
[2,3,5,13,89,233,1597]
(0.03 secs, 2392132 bytes)
*Main> take 8 (same fibs primes)
[2,3,5,13,89,233,1597,28657]
(0.98 secs, 54874800 bytes)

обаче не съвсем бързо 9-тото =-)

*Main> take 9 (same fibs primes)
[2,3,5,13,89,233,1597,28657,514229]
(35.59 secs, 1976699728 bytes)

19.08.2009 (променeно 19.08.2009)

Славомир Къслев