Haskell中单子上下文下无限表的懒惰性

ycggw6v2 于 9个月前发布在其他

关注(0)|答案(2)|浏览(81)

我目前是第一次学习haskell，我在理解懒惰评估方面遇到了很多困难。
主要的问题是，在下面的场景中，有些是懒惰的，有些不是，我不能解释为什么他们中的任何一个这样做。
我将使用的一元函数或iterateM函数定义如下。

iterateM :: (Monad m) => (a -> m a) -> a -> m [a]
iterateM f v = f v >>= go
  where go v' = (v' :) <$> iterateM f v'

场景1

something :: IO [Int]
something = return [1 ..]
take 5 <$> something -- Fine

上面的作品与任何monads（至少从我的实验）。

场景2

something :: Product [Int]
something = iterateM return 5
take 5 <$> something -- Fine

以上与Identity、Sum等一起工作。

场景3

something :: IO [Int]
something = iterateM return 5
take 5 <$> something -- Infinite Loop !

上面用List、Maybe等无限循环。
我做了一些其他的实验，涉及unsafePerformIO在计算某个值时打印，最后怀疑某些函子的**fmap实现需要完全计算右侧，这打破了懒惰**。然而，当我清楚地将fmap应用于take 5时，为什么 * 场景1* 不会无限循环？为什么这会成为IO monad的一个案例呢？
那么，为什么上述情景会以这种方式发生呢？
--编辑-
感谢所有有用的答案，现在我明白发生了什么。我的理解实际上是以非常概念和数学的方式接近的。对于将来的任何参考，我会写下我是如何理解它的。

我的解释-
IO类型相当于IO a = World -> (World, a)。这可以粗略地认为是两个单独的函数，transformation t :: (World -> World)和product p :: (World -> a)只是组合成元组。
让我们考虑IO函子，或者IO类型的fmap函数。它的类型签名为(a -> b) -> IO a -> IO b。如果你把它解释为函数接受一个要fmapped的函数f，一个世界变换t，乘积函数p，并返回一些世界变换，和新的乘积函数，它变得有点容易实现。您只需保持转换不变，并将f与p合成为product。

fmap :: (a -> b) -> IO a -> World -> (World, b)
fmap f x world =
  let newT = t
      newP = f . p in
    (newT world, newP world)
  where
    t = fst . x
    p = snd . x

现在考虑IO monad的μ transform，或join函数。它的类型签名为IO (IO a) -> IO a，相当于(World -> (World, IO a)) -> (World -> (World, a))。这看起来有点吓人，但如果你把tuple看作两个独立的函数，你有t1 :: World -> World，p1 :: World -> IO a，p1的返回值包含两个函数t2 :: World -> World，p2 :: World -> (World, a)。现在，join如何为IO monad实现变得很明显了。

join :: IO (IO a) -> World -> (World, a)
join x world =
  let newT = t2 . t1
      newP = p2 . t1 in
    (newT world, newP world)
  where
    t1 :: World -> World
    t2 :: World -> World
    p2 :: World -> a
    t1 = fst . x
    p1 = snd . x
    t2 = fst . p1
    p2 = snd . p1

定义了join后，绑定函数>>=可以定义为：

=<< :: (a -> IO b) -> IO a -> IO b
=<< = join . fmap

>>= :: IO a -> (a -> IO b) -> IO b
>>= = flip (=<<)

这意味着它的转换函数是第一个参数和第二个参数的返回值的组合。
我们几乎到了那里，让我们考虑一下η变换，或return函数。很简单

return :: a -> World -> (World, a)
return x world =
  let newT = id
      newP = const x
    (newT world, newP world)

现在再次参考场景3。

iterateM :: (Monad m) => (a -> m a) -> a -> m [a]
iterateM f v = f v >>= go
  where go v' = (v' :) <$> iterateM f v'

something :: IO [Int]
something = iterateM return 5
take 5 <$> something

something的转换函数是什么？好的，因为它在执行bind函数，我们可以认为它是f v的t1的组合，f v是id，t2是go的返回值。那么go返回值的转换函数是什么？好吧，我们fmap的东西，所以它将是相同的右手边...这就是无限循环。本质上，它是id s的无限组合。
请注意，乘积函数也是(5 :)和id的无限组合。向左无限合成没有问题，例如... . (5 :) . (5 :)，但产品也向右无限合成id s。
我想这就是威廉的意思
IO是一个monad，它也被定义为以特定的顺序运行。
功能按特定顺序组成，以确保IO按特定顺序执行。如果你无限迭代，它将无限合成。
此外，场景3不使用List或Maybe是相当简单的。Maybe monad的join函数需要知道右侧是Just还是Nothing。实际上，由于这样的属性，它甚至被记录为Haskell Wiki中的惰性破坏者。List monad只是我愚蠢。Listfmap需要知道右侧的第n个元素，以便推断返回值的第n个元素。仔细看代码，它不能推导出任何元素。
场景1当然会起作用，因为IO monad本身并没有神奇地打破内在值的惰性，但是合成乘积和转换函数可以。
当然，上面的代码并不是haskell的IO的实际实现，因为你不能真正捕获World并在现实世界中应用操作。但从概念上讲，它解释了。

haskell

来源：https://stackoverflow.com/questions/76895187/laziness-of-infinite-lists-under-monadic-context-in-haskell

2条答案

按热度按时间

nzkunb0c1#

要理解递归函数是何时定义的，可以用undefined替换它的所有递归调用，并查看结果是undefined（或无限循环或其他错误）（在这种情况下递归函数是undefined），还是一些可能的部分值（在这种情况下递归函数至少是这样定义的）。
iterate f v在<$>（和>>=）下递归调用iterate f v'。因此，这是否被定义取决于<$>（和>>=）的严格性（惰性），也就是说，下面的等式是否成立：

f <$> undefined = undefined

对于Identity（与Sum和Product相同），如果函数参数是非严格的，则<$>是非严格的。（Identity构造函数是一个newtype构造函数，它在运行时不存在，因此不影响严格性。

f <$> Identity x = Identity (f x)

让我们计算iterate return 5。下面的前两个步骤不依赖于单子（第一步是简单地展开定义，第二步是单子定律）：

iterate return 5
  = return 5 >>= \v -> ((v :) <$> iterate return v)
  = (5 :) <$> iterate return 5

为了判断是否定义了它，我们将右侧对iterate的递归调用替换为undefined。

(5 :) <$> undefined

对于Identity，这是一个新类型，undefined = Identity undefined（Identity模式不强制其内容。）

(5 :) <$> undefined = (5 :) <$> Identity undefined = Identity (5 : undefined)

因此iterate return 5至少等于Identity (5 : undefined)。进一步的近似可以通过用该部分结果代替undefined并重复来获得。
相比之下，IO具有严格的<$>：undefined :: IO a是一个崩溃程序，应用<$>只会产生另一个崩溃程序。

iterate return 5 = (5 :) <$> iterate return 5

将对iterate的递归调用替换为undefined

((5 :) <$> undefined) = undefined

因为<$>对于IO是严格的。因此iterate return 5 :: IO [Int]是undefined。

赞(0）回复(0）举报 9个月前

sqougxex2#

主要问题是>>=，这取决于它的功能。对于Product，Monad示例实现为：

instance Monad Product where
    m >>= k  = k (getProduct m)

因此

iterateM f v = go (getProduct (Product v))
  where go v' = (v' :) <$> iterateM f v'

我们可以远程调用Product和getProduct函数，因为它们只是从数据构造函数中 Package 和展开它。

iterateM f v = go v
  where go v' = (v' :) <$> iterateM f v'

或因此：

iterateM f v = go
  where go = (v' :) <$> go

因此，它将把v'前置到 Package 在go中的列表。对于Product，右手边是什么并不重要：我们知道它只能是一个产品，我们也不需要计算Product中 Package 的值，因为我们只是将函数调用（这里是(v' :)）留给一个可能仍然需要计算的值。
因此，这意味着对于一个包含未定义值的Product，甚至一个undefined乘积，我们得到：

(take 1 . (0:) <$> (undefined :: Product [Int]))
Product {getProduct = [0]}

现在对于IO来说，情况并非如此，IO是一个monad，它也被定义为以特定顺序运行：因此，它防止在第一个字节之前将第二个字节写入文件，因为惰性求值以某种方式首先求值第二个字节：它的主要功能是保证评估的顺序（仅对于IO操作）保持不变。
但是对于IO，这意味着如果你有f v >>= go，它将首先运行f v，然后 * go，由于go最终是另一个f v >>= go，因此你会在计算结束之前继续产生要执行的操作，因此它会陷入无限循环。

赞(0）回复(0）举报 9个月前

我来回答

Haskell中单子上下文下无限表的懒惰性

2条答案

相关问题

热门标签

最新问答