玩无穷 - 懒惰的算术 [英] Playing with infinity - Lazy arithmetics

问题描述

示例[Python]：

  EvenSquareNumbers =（x * x for x in naturals（）if x mod 2 == 0）
  

这样的列表可以存在，因为只计算实际需要的元素。 （懒惰评估）

我只是想知道是否有可能（甚至在某些语言中实践过）将懒惰评估的机制扩展到算法。

示例：
给定偶数的无限列表 evens = [x | x< - [1 ..]，甚至x]
我们无法计算

 <$ c 
 
 
 
 $ b $ p 
 
 $ p 
 $ b pre 
 $ b $ p 
 $ b 
但我们实际上可以确定 
 
 
 长度均等> 42 
  
无需评估整个长度术语。  
 
 
这是可能的任何语言吗？哈斯克尔怎么样？
 
 
 
编辑：为了让这个观点更清晰：问题不在于如何确定一个懒惰列表是否比给定数字短。这是关于如何使用传统的内置函数来进行数值计算的延迟。
 
 
  sdcvvc显示了Haskell的解决方案：
 数据Nat = Zero | Succ Nat派生（Show，Eq，Ord）
 
 toLazy :: Integer  - > Nat 
 toLazy 0 =零
 toLazy n = Succ（toLazy（n-1））
 
实例Num Nat其中
（+）（Succ x）y = Succ（x + y）
（+）零y = y 
（*）零y =零
（*）x零=零
（*）（Succ x） y = y +（x * y）
 fromInteger = toLazy 
 abs = id 
 negate =错误Natural only
 signum Zero = Zero 
 signum（Succ x ）= Succ Zero 
 
 len [] = Zero 
 len（_：x'）= Succ $ len x'
 
  -  Test 
 
 len [1 ..]< 42 
  
这在其他语言中也可能吗？ 
 
 
 
 
 数据Nat => 
零| Succ Nat派生（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在无限列表上无效是至关重要的。你可以做一些算术运算（未测试）：
 
 $ $ p $ $ code实例Num Nat其中
（+）（Succ x ）y = Succ（x + y）
（+）零y = y 
（*）零y =零
（*）x零=零
 Succ x）y = y +（x * y）
 fromInteger = toLazy 
 abs = id 
 negate = errorNatural only
 signum Zero = Zero 
 signum （Succ x）= Succ Zero 
  

例如，2 * infinity + 3是无穷大：

  let infinity = Succ无穷
 
 * Main> 2 * infinity + 3 
（Succ（Succ（Succ ^ cCc（Succ（Succ（SuccInterrupted。
  

第二种解决方案

另一种解决方案是使用（）的列表作为懒惰自然数。

  len = map（const（））
 toLazy n = replicate n（）
a = len [1 ..]> toLazy 42 
  

检查

Edit2 ：

将第二个解决方案翻译成Python：

  import itertools 
 
 def length（x）：
返回itertools.imap（lambda：（），x）
 
 def to_lazy（n）：
返回itertools。链（[（）] * n）
  

要添加数字，请使用itertools.chain，使用itertools.product，这不像Haskell那么漂亮，但它有效。

在任何其他严格的语言中，使用cl osures，你可以使用type（） - > a而不是a来模拟懒惰。使用它可以将第一个解决方案从Haskell翻译成其他语言。然而，这将很快变得不可读。

另见一篇很好的Python单行文章。

Many modern programming languages allow us to handle potentially infinite lists and to perform certain operations on them.

Example [Python]:

EvenSquareNumbers = ( x * x for x in naturals() if x mod 2 == 0 )

Such lists can exist because only elements that are actually required are computed. (Lazy evaluation)

I just wondered out of interest whether it's possible (or even practised in certain languages) to extend the mechanism of lazy evaluation to arithmetics.

Example: Given the infinite list of even numbers evens = [ x | x <- [1..], even x ] We couldn't compute

length evens

since the computation required here would never terminate.

But we could actually determine that

length evens > 42

without having to evaluate the whole length term.

Is this possible in any language? What about Haskell?

Edit: To make the point clearer: The question is not about how to determine whether a lazy list is shorter than a given number. It's about using conventional builtin functions in a way that numeric computation is done lazily.

sdcvvc showed a solution for 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 

Is this also possible in other languages?

解决方案

You can create your own natural numbers...

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

Then a is True, thanks to lazy evaluation. It's crucial that len uses foldr, foldl doesn't work on infinite lists. And you can do some arithmetic too (not tested):

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

For example, 2 * infinity + 3 is infinity:

let infinity = Succ infinity

*Main> 2 * infinity + 3
(Succ (Succ (Succ ^cCc (Succ (Succ (SuccInterrupted.

Second solution

Another solution is to use lists of () as lazy natural numbers.

len = map (const ())
toLazy n = replicate n () 
a = len [1..] > toLazy 42

Check Hackage.

Edit: Added instance Num.

Edit2:

Translation of second solution to Python:

import itertools

def length(x):
    return itertools.imap(lambda: (), x) 

def to_lazy(n):
    return itertools.chain([()] * n)

To add numbers, use itertools.chain, to multiply, use itertools.product. This isn't as pretty as in Haskell, but it works.

In any other strict language with closures, you can simulate laziness using the type () -> a instead of a. Using that it is possible to translate the first solution from Haskell to other languages. This will quickly get unreadable, however.

See also a nice article on Python one-liners.

这篇关于玩无穷 - 懒惰的算术的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！