Haskell中的免费问题 [英] Point Free problems in Haskell

问题描述

  bar fg xs = filter 
 
我试图将下面的haskell代码转换为自由风格，没有用处。 f（map g xs）
  

我是haskell的新手，任何帮助都很棒

解决方案

转换为无点风格可以完全机械地完成，尽管很难理解Haskell语法的基本原理，比如左关联函数应用程序和 x + y 与（+）xy 相同。我会假设你对Haskell语法很熟悉;如果没有，我建议首先阅读 LYAH 的前几章。

您需要以下组合器，它们位于标准库中。我还从combinator微积分中给出了它们的标准名称。

  id :: a  - > a  -  I 
 const :: a  - > b  - > a  -  K 
（。）::（b  - > c） - > （a  - > b） - > （a→c）-B 
 flip ::（a→b→c）→> （b→a→c）→C 
（*）::（a→b→c）→ （a  - > b） - > （a  - > c） -  S 
  

一次处理一个参数。将左侧的参数移动到右侧的lambdas，例如

  fxy = Z 
  

成为

  f = \x  - > ; \y  - > Z 
  

我喜欢一次完成这一个参数，而不是一次完成，它看起来更干净。

然后根据以下规则消除刚创建的lambda。

1. 如果您有 \，那么您可以使用小写字母表示字面变量，大写字母表示更复杂的表达式。 x - > x ，替换为 id


2. 如果您有 \x - > ;一个，其中 A 是不存在 x 的任何表达式，用 const A


3. 如果您有 \x - > A ，其中 x 不会出现在 A 中，替换为 A 。这就是所谓的eta收缩。


4. 如果您有 \x - > AB ，则
   
   
   
   
   1. 如果在<$ c $中出现 x c> A 和 B ，替换为（\ x - > A）*< （\ x - > B）。
   
   
   2. 如果 x c> A ，用替换（\ x - > A）B
   
   
   3. code> x 出现在 B 中，替换为 A。 （\ x - > B），
   
   
   4. 如果 x c $ c> A 或 B ，那么还有另外一个规则我们应该已经用过了。
   
   

然后向内工作，消除您创建的lambdas。让我们看看这个例子：

  fxyz = foo z（bar xy）
  - 将参数移动到lambda：
fxy = \z  - > foo z（bar x y）
  - 请记住，该应用程序是左关联的，因此它与
相同f x y = \ z  - > （foo z）（bar xy）
  -  z出现在左边而不是右边，使用flip 
fxy = flip（\ z  - > foo z）（bar xy）
  - 使用规则（3）
fxy = flip foo（bar xy）
 
  - 下一个参数
fx = \y  - > flip foo（bar x y）
  - 应用程序是左关联的
 f x = \y  - > （flip foo）（bar x y）
  -  y出现在右边而不是左边，使用（。）
 f x = flip foo。 （\y-> bar x y）
  - 使用规则3 
 f x =翻转foo。 bar x 
 
  - 下一个参数
 f = \ x  - >翻转foo。 bar x 
  - 我们需要将此运算符重写为正常的应用程序样式
 f = \ x  - > （。）（flip foo）（bar x）
  - 应用程序是左关联的
 f = \ x  - > （（。）（flip foo））（bar x）
  -  x出现在右边但不是左边，使用（。）
 f =（（。）（flip foo））。 （\ x  - > bar x）
  - 使用规则（3）
 f =（（。）（flip foo））。 bar 
  - 冗余括号
 f =（。）（flip foo）。 bar 
  

现在就去尝试一下吧！决定使用哪种规则并没有真正的巧妙：使用适用的任何规则，并且您将取得进展。

I am trying to convert the following haskell code to point free style, with no avail.

bar f g xs = filter f (map g xs )

I am new to haskell and any help would be great

解决方案

Converting to pointfree style can be done entirely mechanically, though it's hard without being comfortable with the fundamentals of Haskell syntax like left-associative function application and x + y being the same as (+) x y. I will assume you are comfortable with Haskell syntax; if not, I suggest going through the first few chapters of LYAH first.

You need the following combinators, which are in the standard library. I have also given their standard names from combinator calculus.

id :: a -> a                                   -- I
const :: a -> b -> a                           -- K
(.) :: (b -> c) -> (a -> b) -> (a -> c)        -- B
flip :: (a -> b -> c) -> (b -> a -> c)         -- C
(<*>) :: (a -> b -> c) -> (a -> b) -> (a -> c) -- S

Work with one parameter at a time. Move parameters on the left to lambdas on the right, e.g.

f x y = Z

becomes

f = \x -> \y -> Z

I like to do this one argument at a time rather than all at once, it just looks cleaner.

Then eliminate the lambda you just created according to the following rules. I will use lowercase letters for literal variables, uppercase letters to denote more complex expressions.

1. If you have \x -> x, replace with id
2. If you have \x -> A, where A is any expression in which x does not occur, replace with const A
3. If you have \x -> A x, where x does not occur in A, replace with A. This is known as "eta contraction".
4. If you have \x -> A B, then
   1. If x occurs in both A and B, replace with (\x -> A) <*> (\x -> B).
   2. If x occurs in just A, replace with flip (\x -> A) B
   3. If x occurs in just B, replace with A . (\x -> B),
   4. If x does not occur in either A or B, well, there's another rule we should have used already.

And then work inward, eliminating the lambdas that you created. Lets work with this example:

f x y z = foo z (bar x y)
-- Move parameter to lambda:
f x y = \z -> foo z (bar x y)
-- Remember that application is left-associative, so this is the same as
f x y = \z -> (foo z) (bar x y)
-- z appears on the left and not on the right, use flip
f x y = flip (\z -> foo z) (bar x y)
-- Use rule (3) 
f x y = flip foo (bar x y)

-- Next parameter
f x = \y -> flip foo (bar x y)
-- Application is left-associative
f x = \y -> (flip foo) (bar x y)
-- y occurs on the right but not the left, use (.)
f x = flip foo . (\y -> bar x y)
-- Use rule 3
f x = flip foo . bar x

-- Next parameter
f = \x -> flip foo . bar x
-- We need to rewrite this operator into normal application style
f = \x -> (.) (flip foo) (bar x)
-- Application is left-associative
f = \x -> ((.) (flip foo)) (bar x)
-- x appears on the right but not the left, use (.)
f = ((.) (flip foo)) . (\x -> bar x)
-- use rule (3)
f = ((.) (flip foo)) . bar
-- Redundant parentheses
f = (.) (flip foo) . bar

There you go, now try it on yours! There is not really any cleverness involved in deciding which rule to use: use any rule that applies and you will make progress.

这篇关于Haskell中的免费问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！