哈斯克尔教会名单上的操作 [英] Operations on Church Lists in Haskell

问题描述

我指的是这个问题

  type Churchlist tu =（t-> u-> u） - > u-> u 
   
 
  [p $ p 
 
 
 ]：=λc。 λN。 n 
 [1,2,3]：=λc。 λN。 c 1（c 2（c 3 n））
 
 mapChurch ::（t-> s） - > （Churchlist t u） - > （Churchlist s u）
 mapChurch f l = \c n  - > l（cf）n 
  
我正在考虑我可以在Churchlists上实现的其他列表函数并成功编写conc2函数连接2个教会名单
 
 
  conc2Church l1 l2 cn = l1 c（l2 cn）
  
我也尝试了一个zipWithChurch，它在普通列表上像zipWith一样运行。但我找不到解决方案。任何人都可以帮助我吗？
解决方案
你想使用真正的元组还是教会元组？我会假设前者。 
 
 
因此，从所需的类型签名开始。你希望它取得两个不同的 Churchlist  s并产生一个 Churchlist 元组。
  churchZip :: Churchlist au  - > Churchlist b u  - > Churchlist（a，b）u 
  
现在你将如何实现这个？回想一下， Churchlist 由折叠它们的函数表示。因此，如果我们的结果是一个 Churchlist（a，b）u ，我们希望它具有类型（（ a，b） - > u  - > u） - > u  - > （毕竟，这是相当于类型同义词 Churchlist（a，b）> ）。
 
 
  churchZip l1 l2 cn = ??? 
  
下一步是什么？那么，这取决于。是 l1 为空吗？那么 l2 ？如果其中任何一个都是，那么你希望结果是空的列表。否则，您想要将每个列表中的第一个元素配对，然后将其他教会的草稿加以配对。 
 
 
  churchZip l1 l2 cn 
 | isEmpty l1 || isEmpty l2 = n 
 |否则= c（churchHead l1，churchHead l2）
（churchZip（churchTail l1）（churchTail l2）cn 
  
这带来了一些问题。 
 
 
 
 
你可以递归地写这个函数吗？在纯lambda演算中， 
 
您是否有 churchHead ， churchTail 和 isEmpty 可用吗？您是否愿意编写它们？您可以编写它们吗？
 
是否有更好的方式来构造这个函数？任何事情都可以用fold来实现（记住， l1 和 l2 实际上 
           纯粹是机械的，假设对教会编码列表有一个牢固的理解，我会把深思想留给你，因为是作业。
 
I am referring to this question
type Churchlist t u = (t->u->u)->u->u
In lambda calculus, lists are encoded as following:
[] := λc. λn. n
[1,2,3] := λc. λn. c 1 (c 2 (c 3 n))

mapChurch :: (t->s) -> (Churchlist t u) -> (Churchlist s u)
mapChurch f l = \c n -> l (c.f) n
I am thinking about what other list functions I could implement on Churchlists and successfully wrote a conc2 function that concatenates 2 church lists
conc2Church l1 l2 c n = l1 c (l2 c n)
I also tried a zipWithChurch that operates like zipWith on normal lists. But i can not find a solution. Can anyone help me?
解决方案
Do you want to use real tuples, or church tuples? I'll assume the former.

So, start with the desired type signature. You want it to take in 2 different Churchlists and produce a Churchlist of tuples.
churchZip :: Churchlist a u -> Churchlist b u -> Churchlist (a,b) u
Now how would you implement this? Recall that Churchlists are represented by the function that folds over them. So if our result is a Churchlist (a,b) u, we'll want it to have the form of a function of the type ((a,b) -> u -> u) -> u -> u (this is, after all, the equivalent to the type synonym Churchlist (a,b) u).
churchZip l1 l2 c n = ???
What is the next step? Well, that depends. Is l1 empty? What about l2? If either of them are, then you want the result to be the empty list. Otherwise, you want to pair up the first elements from each list, and then churchZip the rest.
churchZip l1 l2 c n
  | isEmpty l1 || isEmpty l2 = n
  | otherwise                = c (churchHead l1, churchHead l2)
                                 (churchZip (churchTail l1) (churchTail l2) c n
This brings up some questions.


Are you allowed to write this function recursively? In the pure lambda calculus, you must write recursive functions with the fixpoint operator (aka the y combinator).
Do you have churchHead, churchTail, and isEmpty available? Are you willing to write them? Can you write them?
Is there a better way to structure this function? Anything can be done with a fold (remember, l1 and l2 actually are the folding function over themselves), but is that a clean solution to this problem?


Getting up to this point is purely mechanical, assuming a firm understanding of the church encoding of lists. I'll leave the deep thinking up to you, since this is homework.

                        
这篇关于哈斯克尔教会名单上的操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！