在折叠式树状结构的类型球拍中强制转换为任意类型 [英] Casting to arbitrary type in Typed Racket folding a Tree

问题描述

我正在尝试生成一个类型化的Racket过程，该过程对于某些类型的 A ，一个 Tree 和一个来自两个 A 的函数传递给 A 的另一个参数 A ，并返回类型为 A 的值.我对(全部)语法不是很熟悉，但是我尝试使用它.不幸的是，我的代码在构建时会产生以下错误消息:

I'm trying to produce a typed Racket procedure that for some type A, takes a Tree, and a function from two As to an A, another parameter of type A, and returns a value of type A. I'm not very familiar with the (All) syntax, but I tried using it. Unfortunately, my code produces the following error message at build-time:

Type Checker: Polymorphic function `foldr' could not be applied to arguments:
Types: (-> a b b) b (Listof a)  -> b
       (-> a b c c) c (Listof a) (Listof b)  -> c
       (-> a b c d d) d (Listof a) (Listof b) (Listof c)  -> d
Arguments: (-> A A A) A (Listof Any)
Expected result: A

我的代码:

(: fold : (All (A) (Instance Tree) (A A -> A) A -> A))
(define (fold tree f base)
  (foldr
    f
    base
    (cons
      (value tree)
      (map 
        (lambda
          ([tree : (Instance Tree)])
          (fold tree f base)
          ) 
        (children tree)
        )
      )
    )
  )

我试图简化该功能，直到它开始起作用，这才是它开始起作用的地方:

I tried to simplify the function until it started to work, and this was where it started working:

(: fold : (All (A) (Instance Tree) (A A -> A) A -> A))
(define (fold tree f base)
  (foldr f base (list base))
)

我认为正在发生的事情是类型检查器不知道(值树)也是 A 类型.有什么办法可以使(Cast)成为 A 类型?如果没有，我将如何解决这个问题?

I think what's happening is that the type checker doesn't know that (value tree) is also of type A. Is there any way I can (Cast) it to be of type A? If not, how would I approach getting this to work?

推荐答案

结构类型定义如答案通过 tfb ，

#lang typed/racket

(struct (A) tree
  ((value : A)
   (children : (Listof (Treeof A))))
  #:type-name Treeof)

以下定义有效(某种程度上):

the following definition works (somewhat):

(: fold-tree (All (A R) (-> (Treeof A) (-> A R R) R R)))
(define (fold-tree tree f base)
  (f (tree-value tree)
     (foldr
          (lambda ((child : (Treeof A)) (r : R))
            (fold-tree child f r))
          base
          (tree-children tree))))

现在在交互"窗口中尝试

Now trying it in the interactions window,

(fold-tree (tree 1 (list (tree 2 '()))) + 0)

工作并返回

- : Integer [more precisely: Nonnegative-Integer]
3

但尝试看似等效的

(fold-tree (tree 1 (list (tree 2 '()))) (lambda (a r) (+ a r)) 0)

带来很多错误.

更新:由于tfb的输入，以下调用全部工作:

update: thanks to tfb's input, the following calls all work:

> (fold-tree (tree 1 (list (tree 2 '()))) (lambda ((a : Number) (r : Number)) (+ a r)) 0)
- : Number
3

> (fold-tree (tree 1 (list (tree 2 '()))) (lambda ((a : Any) (b : Any)) (cons a b)) 0)
- : (U Zero (Pairof Any Any))
'(1 2 . 0)

> (fold-tree (tree 1 (list (tree 2 '()))) (lambda ((a : Any) (b : Any)) (cons a b)) '())
- : (U Null (Pairof Any Any))
'(1 2)

> (fold-tree (tree 1 (list (tree 2 '()))) (lambda ((a : Any) (b : (Listof Any)))
     (cons a b)) '())
- : (Listof Any)
'(1 2)

> (fold-tree (tree 1 (list (tree 2 '()))) (lambda ((a : Number) (b : (Listof Number))) 
     (cons a b)) '())
- : (Listof Number)
'(1 2)

> (fold-tree (tree 1 (list (tree 2 '()))) (lambda (a b) (cons a b)) '())
- : (U Null (Pairof Any Any))
'(1 2)

> (fold-tree (tree 1 (list (tree 2 '()))) cons '())
*** Type Checker: Polymorphic function `fold-tree' could not be applied to arguments:
Argument 1:
  Expected: (Treeof A)
  Given:    (Treeof Positive-Byte)
Argument 2:
  Expected: (-> A R R)
  Given:    (All (a b) (case-> (-> a (Listof a) (Listof a)) (-> a b (Pairof a b))))
Argument 3:
  Expected: R
  Given:    Null
 in: (fold-tree (tree 1 (list (tree 2 (quote ())))) cons (quote ()))
> 

这篇关于在折叠式树状结构的类型球拍中强制转换为任意类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！