Игра с бесконечностью — Ленивая арифметика
-
12-09-2019 - |
Вопрос
Многие современные языки программирования позволяют нам обрабатывать потенциально бесконечные списки и выполнять над ними определенные операции.
Пример [Питон]:
EvenSquareNumbers = ( x * x for x in naturals() if x mod 2 == 0 )
Такие списки могут существовать, поскольку вычисляются только те элементы, которые действительно необходимы.(ленивая оценка)
Я просто из интереса поинтересовался, возможно ли (или даже практикуется ли в некоторых языках) распространить механизм ленивых вычислений на арифметику.
Пример:Учитывая бесконечный список четных чисел evens = [ x | x <- [1..], even x ]
Мы не могли вычислить
length evens
поскольку требуемые здесь вычисления никогда не завершатся.
Но на самом деле мы могли бы определить это
length evens > 42
без необходимости оценивать все length
срок.
Возможно ли это на каком-либо языке?А как насчет Хаскелла?
Редактировать:Чтобы прояснить ситуацию:Вопрос не в том, как определить, короче ли ленивый список заданного числа.Речь идет об использовании обычных встроенных функций таким образом, чтобы числовые вычисления выполнялись лениво.
sdcvvc показал решение для Haskell:
data Nat = Zero | Succ Nat deriving (Show, Eq, Ord)
toLazy :: Integer -> Nat
toLazy 0 = Zero
toLazy n = Succ (toLazy (n-1))
instance Num Nat where
(+) (Succ x) y = Succ (x + y)
(+) Zero y = y
(*) Zero y = Zero
(*) x Zero = Zero
(*) (Succ x) y = y + (x * y)
fromInteger = toLazy
abs = id
negate = error "Natural only"
signum Zero = Zero
signum (Succ x) = Succ Zero
len [] = Zero
len (_:x') = Succ $ len x'
-- Test
len [1..] < 42
Возможно ли это и на других языках?
Решение
Вы можете создавать свои собственные натуральные числа...
data Nat = Zero | Succ Nat deriving (Show, Eq, Ord)
len :: [a] -> Nat
len = foldr (const Succ) Zero
toLazy :: Int -> Nat
toLazy 0 = Zero
toLazy n = Succ (toLazy (n-1))
a = len [1..] > toLazy 42
Тогда a истинно благодаря ленивому вычислению.Крайне важно, чтобы len использовал Foldr, Foldl не работает с бесконечными списками.И вы тоже можете выполнить некоторые арифметические действия (не проверялось):
instance Num Nat where
(+) (Succ x) y = Succ (x + y)
(+) Zero y = y
(*) Zero y = Zero
(*) x Zero = Zero
(*) (Succ x) y = y + (x * y)
fromInteger = toLazy
abs = id
negate = error "Natural only"
signum Zero = Zero
signum (Succ x) = Succ Zero
Например, 2*бесконечность + 3 — бесконечность:
let infinity = Succ infinity
*Main> 2 * infinity + 3
(Succ (Succ (Succ ^cCc (Succ (Succ (SuccInterrupted.
Второе решение
Другое решение — использовать списки () в качестве ленивых натуральных чисел.
len = map (const ())
toLazy n = replicate n ()
a = len [1..] > toLazy 42
Проверять Хакадж.
Редактировать:Добавлен экземпляр Num.
Редактировать2:
Перевод второго решения на Python:
import itertools
def length(x):
return itertools.imap(lambda: (), x)
def to_lazy(n):
return itertools.chain([()] * n)
Для сложения чисел используйте itertools.chain, для умножения — itertools.product.Это не так красиво, как в Haskell, но работает.
В любом другом строгом языке с замыканиями вы можете имитировать ленивость, используя тип () -> a вместо a.Используя это, можно перевести первое решение с Haskell на другие языки.Однако это быстро станет нечитаемым.
Смотрите также хорошая статья об однострочниках Python.
Другие советы
Если бы не лень, думаю, в F# это сработало бы:
type Nat = Zero | Succ of Nat
let rec toLazy x =
if x = 0 then Zero
else Succ(toLazy(x-1))
type Nat with
static member (+)(x:Nat, y:Nat) =
match x with
| Succ(a) -> Succ(a+y)
| Zero -> y
static member (*)(x:Nat, y:Nat) =
match x,y with
| _, Zero -> Zero
| Zero, _ -> Zero
| Succ(a), b -> b + a*b
module NumericLiteralQ =
let FromZero() = toLazy 0
let FromOne() = toLazy 1
let FromInt32(x:int) = toLazy x
let rec len = function
| [] -> 0Q
| _::t -> 1Q + len t
printfn "%A" (len [1..42] < 100Q)
printfn "%A" (len [while true do yield 1] < 100Q)
Но поскольку нам нужно быть ленивыми, это расширяется до этого:
let eqLazy<'T> (x:Lazy<'T>) (y:Lazy<'T>) : bool = //'
let a = x.Force()
let b = y.Force()
a = b
type Nat = Zero | Succ of LazyNat
and [<StructuralComparison(false); StructuralEqualityAttribute(false)>]
LazyNat = LN of Lazy<Nat> with
override this.GetHashCode() = 0
override this.Equals(o) =
match o with
| :? LazyNat as other ->
let (LN(a)) = this
let (LN(b)) = other
eqLazy a b
| _ -> false
interface System.IComparable with
member this.CompareTo(o) =
match o with
| :? LazyNat as other ->
let (LN(a)) = this
let (LN(b)) = other
match a.Force(),b.Force() with
| Zero, Zero -> 0
| Succ _, Zero -> 1
| Zero, Succ _ -> -1
| Succ(a), Succ(b) -> compare a b
| _ -> failwith "bad"
let (|Force|) (ln : LazyNat) =
match ln with LN(x) -> x.Force()
let rec toLazyNat x =
if x = 0 then LN(lazy Zero)
else LN(lazy Succ(toLazyNat(x-1)))
type LazyNat with
static member (+)(((Force x) as lx), ((Force y) as ly)) =
match x with
| Succ(a) -> LN(lazy Succ(a+ly))
| Zero -> lx
module NumericLiteralQ =
let FromZero() = toLazyNat 0
let FromOne() = toLazyNat 1
let FromInt32(x:int) = toLazyNat x
let rec len = function
| LazyList.Nil -> 0Q
| LazyList.Cons(_,t) -> LN(lazy Succ(len t))
let shortList = LazyList.of_list [1..42]
let infiniteList = LazyList.of_seq (seq {while true do yield 1})
printfn "%A" (len shortList < 100Q) // true
printfn "%A" (len infiniteList < 100Q) // false
Это демонстрирует, почему люди пишут подобные вещи только на Haskell.
Вероятно, вы сможете добиться желаемого, попытавшись получить из четов более 42 элементов.
Не уверен, что понимаю ваш вопрос, но давайте попробуем.Возможно, вы ищете потоки.Я говорю только на Эрланге, из языковой семьи FP, так что...
esn_stream() ->
fun() -> esn_stream(1) end.
esn_stream(N) ->
{N*N, fun() -> esn_stream(N+2) end}.
Вызов потока всегда возвращает следующий элемент, и вам следует вызвать функцию fun, чтобы получить следующий элемент.Таким образом вы достигаете ленивой оценки.
Затем вы можете определить функцию is_stream_longer_than как:
is_stream_longer_than(end_of_stream, 0) ->
false;
is_stream_longer_than(_, 0) ->
true;
is_stream_longer_than(Stream, N) ->
{_, NextStream} = Stream(),
is_stream_longer_than(NextStream, N-1).
Результат:
1> e:is_stream_longer_than(e:esn_stream(), 42).
true
2> S0 = e:esn_stream().
#Fun<e.0.6417874>
3> {E1, S1} = S0().
{1,#Fun<e.1.62636971>}
4> {E2, S2} = S1().
{9,#Fun<e.1.62636971>}
5> {E3, S3} = S2().
{25,#Fun<e.1.62636971>}