标签: recursion-schemes

下面是一些代码,我写了一个练习,使用para从recursion-schemes(我知道,这减少的例子也只用得到解决cata,但让我们忽略这个这个问题).

在这样做的时候,我注意到我在使用时必须进行非详尽的模式匹配,para如果我想访问Depth构造函数的任何参数的表达式树.

我找到了一个替代实现,gcata'并且para'没有这个问题,也不需要a Comonad,只需要一个Functor实例w.这让我很好奇:为什么这个版本没有用于执行recursion-schemes？它有什么问题,还是有更好的方法来实现我正在寻找的东西？

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE RankNTypes #-}
module Test where

import Data.Functor
import Data.Functor.Foldable

data ExprF a = Depth a a -- ^ Counts the maximum depth of the tree
             | Unit
  deriving Functor
type Expr = Fix ExprF

unit :: Expr
unit = Fix Unit

depth :: Expr -> …

仍在我的文本编辑器Rasa上工作。

目前，我正在构建用于跟踪视口/拆分的系统（类似于vim拆分）。对我来说，将这种结构表示为一棵树似乎很自然：

data Dir = Hor
         | Vert
         deriving (Show)

data Window a =
  Split Dir SplitInfo (Window a) (Window a)
    | Single ViewInfo a
    deriving (Show, Functor, Traversable, Foldable)

效果很好，我将Views 存储在树中，然后可以在它们上遍历/ fmap来更改它们，这也与镜头包很好地吻合！

我最近一直在学习递归方案，这似乎是一个合适的用例，因为树是递归的数据结构。

我设法弄清楚了，以构建Fixpoint版本：

data WindowF a r =
  Split Dir SplitInfo r r
    | Single ViewInfo a
    deriving (Show, Functor)

type Window a = Fix (WindowF a)

但是，现在Functor实例已被r; 用尽。

我尝试了几种

deriving instance Functor Window

但是它很令人吃惊，因为window是类型的同义词。

和：

newtype Window a = …

我正在阅读Jeremy Gibbons关于折纸编程的文章,我坚持练习3.7,要求读者证明列表的融合法展开:

unfoldL p f g . h = unfoldL p' f' g'

Run Code Online (Sandbox Code Playgroud)

如果

p . h = p'
f . h = f'
g . h = h . g'

Run Code Online (Sandbox Code Playgroud)

unfoldL列表展开的功能定义如下:

unfoldL :: (b -> Bool) -> (b -> a) -> (b -> b) -> b -> List a
unfoldL p f g b = if p b then Nil else Cons (f b) (unfoldL p f g (g b))

这是我目前尝试的证据:

(unfoldL p f …

我一直在看recursion-schemes图书馆,我对prepro应该用于什么,甚至它做什么感到非常困惑.它作为'Fokkinga的prepromorphism'的描述并不是非常有用,并且签名(prepro :: Corecursive t => (forall b . Base t b -> Base t b) -> (Base t a -> a) -> t -> a)看起来非常类似于cata(catamorphism),但有一个额外的参数,其意图不明确.有人能够解释这个函数的意图吗？

我有这个简单的ExprAST,我可以轻松地将其转换为String.

import Prelude hiding (Foldable)
import qualified Prelude
import Data.Foldable as F
import Data.Functor.Foldable
import Data.Monoid
import Control.Comonad.Cofree

data ExprF r = Const Int
              | Add   r r
                deriving ( Show, Eq, Ord, Functor, Prelude.Foldable )

type Expr = Fix ExprF

testExpr = Fix $ Add (Fix (Const 1)) (Fix (Const 2))

convertToString :: Expr -> String
convertToString = cata $ \case
  e@(Const x) -> show x
  e@(Add x y) -> unwords [x, "+", y]

现在我想添加一个额外的数据.所以我想尝试使用 …

我有这种语言AST

data ExprF r = Const Int
              | Var   String
              | Lambda String r
              | EList [r]
              | Apply r r
 deriving ( Show, Eq, Ord, Functor, Foldable )

我想将它转换为字符串

toString = cata $ \case
  Const x -> show x
  Var x -> x
  EList x -> unwords x
  Lambda x y -> unwords [x, "=>", y]
  Apply x y -> unwords [x, "(", y, ")"]

但是当使用lambda时,Apply我需要括号

(x => x)(1)

但我无法将内部结构与cata相匹配

toString :: Fix ExprF -> String
toString …

现在，我有一个 AST 表达式，它在递归类型上是多态的：

data Expr a = Const Int
            | Add a a

这非常有用，它允许我使用一种类型进行普通递归 ( Fix Expr)，而在需要附加额外信息时使用另一种类型( Cofree Expr ann)。

当我想在这个递归方案中引入另一种类型时会出现问题：

data Stmt a = Compound [a]
            | Print (Expr ?)

如果Expr不引入额外的类型变量并破坏与我已经编写的所有通用函数的兼容性，我不确定该术语的内容。

可以这样做吗，如果可以，这是一种有用的模式吗？

我预计下面的代码会立即运行并退出,因为p它实际上从未使用过,但它运行了超过7分钟,然后似乎被操作系统杀死了.

{-# LANGUAGE DeriveFunctor #-}

import Control.Monad (liftM2)

main = print $ ((product' 1 >>= \p -> Nothing) :: Maybe Integer)

data Term f = In { out :: f (Term f) }

type Algebra f a = (f a -> a)

cata :: (Functor f) => Algebra f a -> Term f -> a
cata g t = g $ fmap (cata g) $ out t

type CoAlgebra f a = (a -> f a)

ana :: …

以下函数通过使用递归方案库从列表实现良好的旧过滤器函数.

import Data.Functor.Foldable 

catafilter :: (a -> Bool) -> [a] -> [a] 
catafilter p = cata alg 
  where
    -- alg :: ListF a [a] -> [a]
    alg  Nil  =  []
    alg  (Cons x xs) = if (p x) then x : xs else xs

它编译和短期测试就像catafilter odd [1,2,3,4]是成功的.但是,如果我取消注释类型签名,alg我会收到以下错误:

src/cata.hs:8:30: error:
    • Couldn't match expected type ‘a’ with actual type ‘a1’
      ‘a1’ is a rigid type variable bound by
        the type signature for:
          alg …

我有这个 AST 数据结构

data AST = Integer Int
         | Let String AST AST
         | Plus AST AST
         | Minus AST AST
         | Times AST AST
         | Variable String
         | Boolean Bool
         | If AST AST AST
         | Lambda String AST Type Type
         | Application AST AST
         | And AST AST
         | Or AST AST
         | Quot AST AST
         | Rem AST AST
         | Negate AST
         | Eq AST AST
         | Leq AST AST
         | Geq AST AST
         | Neq AST …