可以用无点样式编写此函数吗?如果没有，为什么? [英] Can this function be written in point-free style? If not, why?

问题描述

一个相关的问题是此，但是有些答案说几乎所有东西都可以成为无积分的，那么这个功能有什么问题呢?

 \[x] -> x
 

http://pointfree.io/似乎无法以无点样式编写.这是否意味着它不能以这种方式编写?如果是这样，其理论原因是什么?

我只能观察到上面的函数是一个残缺的"函数. head(或last，fwiw)的版本，只能在单例列表上运行.实际上，应用于非单例列表时，它会在ghci中以这种方式出错:

 *** Exception: <interactive>:380:5-13: Non-exhaustive patterns in lambda
 

也许非穷举"是指模式上的原因是为什么某些函数不能以无点样式编写?

根据答案进行

我没想到我的问题的答案会如此复杂(我觉得我只是以为简短的答案实际上是不，它不能)，所以我需要花点时间仔细阅读它们，进行一些试验，然后将我的想法环绕在它们周围，否则我无法决定应该接受哪个.暂时将乔恩·普迪(Jon Purdy)的答案+1，直到这是我在普通代码中会停止的地方.

解决方案

当然，几乎所有 都可以做成无指向性的.棘手的事情是在结果表达式中将允许使用哪些函数.如果我们进行模式匹配，则通常需要使用fold函数来进行匹配.因此，例如，如果我们在Maybe a上进行模式匹配，则需要将其替换为this, but some of the answer say that almost anything can be made point free, so what is wrong with this function?

\[x] -> x

http://pointfree.io/ doesn't seem to be able to write it in point-free style. Does this mean that it cannot be written that way? If so, what is the theoretical reason for it?

I can only observe that the function above is a "crippled" version of head (or last, fwiw) which can only operate on singleton lists. Indeed, applied on non singleton lists, it errors this way in ghci:

*** Exception: <interactive>:380:5-13: Non-exhaustive patterns in lambda

Maybe the "non-exhaustivity" on the pattern is the reason why some functions cannot be written in point-free style?

Edit in the light of the answers:

I did not expect that the answers to my question could be so complex (I feel I just thought that the short answer was no, it cannot, actually), so I need to find some time to read them carefully, experiment a bit, and wrap my mind around them, otherwise I cannot decide which one should be accepted. For the time being, +1 to Jon Purdy's answer, which I could easily understand up to This is where I would stop in ordinary code.

解决方案

Sure, pretty much anything can be made pointfree. The tricky thing is what functions you'll allow in the resulting expression. If we pattern match, we generally need a fold function to do the matching instead. So, for instance, if we pattern matched on a Maybe a, we'd need to replace that with maybe. Similarly, Either a b patterns can be written in terms of either.

Note the pattern in the signatures

data Maybe a = Nothing | Just a

maybe :: b -> (a -> b) -> (Maybe a -> b)

Maybe a has two constructors, one which takes no arguments and the other which takes an a. So maybe takes two arguments: one which is a 0-ary function (b), and one which takes an a (a -> b), and then returns a function from Maybe a -> b. The same pattern is present in either

data Either a b = Left a | Right b

either :: (a -> c) -> (b -> c) -> (Either a b -> c)

Two cases. The first takes an a and produces whatever c we want. The second takes a b and produces whatever c we want. In every case, we want one function for each possible term in the sum type.

In order to systematically pointfree a function like \[x] -> x, we'd need a similar fold. [a] is declared as, essentially

data [a] = [] | a : [a]

So we'd need a function with this signature

list :: b -> (a -> [a] -> b) -> ([a] -> b)

Now, flip foldr comes close

flip foldr :: b -> (a -> b -> b) -> ([a] -> b)

But it's recursive. It calls its provided function on the [a] part of a : [a]. We want a true fold, which isn't provided by Haskell's base libraries. A quick Hoogle search tells us that this function does exist in a package though, called extra. Of course, for this small example we can just write it ourselves very easily.

list :: b -> (a -> [a] -> b) -> ([a] -> b)
list f g x = case x of
               [] -> f
               (y:ys) -> g y ys

Now we can apply it to your \[x] -> x easily. First, let's write what your function really does, including all of the messy undefined cases (I'll use undefined rather than a long error message here, for brevity)

func :: [a] -> a
func x = case x of
           [] -> undefined
           (y:ys) -> case ys of
                       [] -> y
                       (_:_) -> undefined

Now every case statement exactly matches each constructor once. This is ripe for transformation into a fold.

func :: [a] -> a
func x = case x of
         [] -> undefined
         (y:ys) -> list y undefined ys

And now we transform the outer case as well

func :: [a] -> a
func x = list undefined (\y -> list y undefined) x

So we have

func :: [a] -> a
func = list undefined (\y -> list y undefined)

Or, if we want to be truly crazy about it

func :: [a] -> a
func = list undefined (flip list undefined)

But this function isn't in base

Yeah, that's true. We kind of cheated by using a fold that didn't exist. If we want to do it systematically, we need that fold operator. But without it, we can still kludge it together with foldr1, which suffices for our particular purposes.

func' :: [a] -> a
func' = foldr1 (const (const undefined))

So, to answer your question, we can't always systematically replace pattern matching like in your example with pointfree, unless we have a fold function with the right signature. Fortunately, that function can always be written, for any Haskell 98 data type (possibly GADTs as well, but I haven't considered that possibility in any depth). But even without that support, we can still make it work, kind of.

这篇关于可以用无点样式编写此函数吗?如果没有，为什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！