标签: recursive-datastructures

我不确定如何在定点之后派生出函数实例:

data FreeF f a next  = PureF a | FreeF (f next)  deriving (Functor)

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

newtype Free f a = Free(  Mu (FreeF f a)  )

instance Functor f => Functor (Free f) where
     fmap h (Free (out -> PureF a))  = Free (In (PureF (h a)))
     fmap h (Free (out -> FreeF fn)) = Free (In (fmap undefined undefined)) --stuck

如果我修改Mu以接受额外的类型参数,我可以继续...直到...:

data Mu f a …

我对Haskell中的递归数据结构有疑问(我目前正在努力学习的语言).

我想用Haskell Prolog之类的术语编码,但我想出的每个解决方案都有不同的缺点,我真的想避免.如果你希望从这个角度来看我的问题,我想找到一种在Haskell类型中编码BNF语法的廉价而优雅的方法.

正如一个提醒,一些序言而言可能是male,sum(2, 3.1, 5.1),btree(btree(0, 1), Variable).

解决方案1

data Term = SConst String
          | IConst Integer
          | FConst Double
          | Var    String
          | Predicate   {predName :: String, predArgs :: [Term]}

使用此解决方案,我可以使用嵌套谓词(因为predArgs是Term),但我无法区分谓词类型签名中的其他术语.

解决方案2

data Term = SConst String
          | IConst Integer
          | FConst Double
          | Var    String

data Predicate = Predicate {predName :: String, predArgs ::[Either Term Predicate}

在这个变体中,我可以清楚地区分谓词和基本术语,但是列表中的Either类型在predArgs后面的代码中管理会非常麻烦(我想......我是Haskell的新手).

解决方案3

data Term = SConst String
          | …

import Data.Attoparsec.Text.Lazy
import Data.Text.Lazy.Internal (Text)
import Data.Text.Lazy (pack)

data List a = Nil | Cons a (List a)

list :: Text
list = pack $ unlines
  [ "0"
  , "1"
  , "2"
  , "5"
  ]

如何List Int解析器coud实现解析Cons 0 (Cons 1 (Cons 2 (Cons 5 Nil)))从list？

ps:纯解析器而不解析a [Int]并将其转换List Int为更好.

我试图用这个问题掌握使用TMP 的递归数据结构生成技术.

题

假设我有一个可变参数模板 template<typename... Ts> struct my_sets { };.

在my_sets我想生成一个数据成员依赖的新类型Ts.

例如,我希望每个元素/类型my_sets都有一个std::set<T>数据成员Ts...

using x_t = my_sets<int,char,std::string>;
x_t x;

x.insert<0>(   5   );  // into a std::set<int> member in my_sets<>
x.insert<1>(  'z'  );  // into a std::set<char> member in my_sets<>
x.insert<2>( "foo" );  // into a std::set<std::string> member in my_sets<>

我认为实现这一目标的一种方法可能是使用子类化和递归,但我不确定.

fwiw,如果通过自由函数或普通函数重载更直接地实现mutator,那也没关系:

insert<0>( x,   5   );  // into a std::set<int> member in my_sets<>
insert<1>( x,  'z'  );  // into …

我正在尝试在Haskell中编写命题逻辑解算器.我用一种名为'Sentence'的递归数据类型表示逻辑表达式,它有几种不同操作的子类型 - 'AndSentence','OrSentence'等等.所以我猜这是一棵树,有几种类型的节点,每个都有0,1,或2个孩子.

它似乎工作,但一些代码是重复的,我认为应该有更好的方式来表达它.基本上我有几个函数,其中'默认行为'是让函数以递归方式对节点的子节点进行操作,从而触底于某些节点类型(通常是'AtomicSentences',即叶子).所以我写了一个函数:

imply_remove :: Sentence Symbol -> Sentence Symbol
imply_remove (ImplySentence s1 s2) = OrSentence (NotSentence (imply_remove s1)) (imply_remove s2)
imply_remove (AndSentence s1 s2) = AndSentence (imply_remove s1) (imply_remove s2)
imply_remove (OrSentence s1 s2) = OrSentence (imply_remove s1) (imply_remove s2)
imply_remove (NotSentence s1) = NotSentence (imply_remove s1)
imply_remove (AtomicSentence s1) = AtomicSentence s1

我想用一种更简洁的方式来编写'AndSentence','OrSentence'和'NotSentence'的行.

似乎仿函数与我想要的类似,但是没有用到......我想对子树进行操作,而不是对子树的每个节点中包含的某些值进行操作.

有没有正确的方法来做到这一点？或者更自然的方式来构建我的数据？

作为练习，我尝试在 monad 内递归地构造一个无限的、惰性的列表。

基本上，相当于nat，但是是一元的，monat：

nat :: Int -> [Int]
nat n = n : nat (n+1)

monat :: Monad m => Int -> m [Int]
monat n = return n >>= \n -> (n:) <$> monat (n+1)

但monat并不是真正懒惰地求值：如果不计算所有元素，就不可能获得第一个元素：

ghci> take 5 $ nat 0
[0,1,2,3,4]

ghci> take 5 <$> (monat 0) :: Maybe [Int]
... never ending computation ...

我怀疑问题一定在于fmapor >>=，因为它们是我在那里使用但不在 中使用的唯一额外函数nat。然而，我查看了他们的实现，但不明白为什么或在哪里打破了懒惰：

instance  Functor Maybe  where
    fmap _ Nothing …

我正在使用递归 glob 来查找文件并将其从一个驱动器复制到另一个驱动器

def recursive_glob(treeroot, pattern):
   results = []
   for base, dirs, files in os.walk(treeroot):

      goodfiles = fnmatch.filter(files, pattern)
      results.extend(os.path.join(base, f) for f in goodfiles)

return results

工作正常。但我还想访问与过滤器不匹配的元素。

有人可以提供一些帮助吗？我可以在循环内构建一个正则表达式，但一定有一个更简单的解决方案，对吧？

我是否需要使用typedef才能构建递归结构？我尝试使用以下代码但没有成功:

struct teste
{
    int data;
    int data2;
    struct teste to_teste;
};

我主要使用Python,但我正在玩Go.我写了以下内容来做一些在python中非常简单的事情,我希望它也可以在Go中完成.

package main

import (
    "bytes"
    "encoding/gob"
    "fmt"
    "io/ioutil"
)

type Order struct {
    Text string
    User *User
}

type User struct {
    Text  string
    Order *Order
}

func main() {
    o := Order{}
    u := User{}
    o.Text = "order text"
    u.Text = "user text"

    // commenting this section prevents stack overflow
    o.User = &u
    u.Order = &o
    fmt.Println("o.u.text:", o.User.Text, "u.o.text:", u.Order.Text)
    // end section

    m := new(bytes.Buffer)
    enc := gob.NewEncoder(m)
    enc.Encode(o)
    err := ioutil.WriteFile("gob_data", m.Bytes(), 0600)
    if err != …

问题

我试图执行修改后的龙形曲线从业务计费16日在哈斯克尔无限名单.

该列表由True和组成False.我们从一些列表开始s0:

• s1 = s0 ++ [False] ++ (map not . reverse) s0
• s2 = s1 ++ [False] ++ (map not . reverse) s1
• s3 = s2 ++ [False] ++ (map not . reverse) s2

通常

sn = s(n-1) ++ [0] ++ (map not . reverse) s(n-1) 
   = s0 ++ [0] ++ (f s0) ++ [0] ++ (f (s0 ++ [0] ++ (f s0))) ++ ...
      where f = …