Is it possible to write pattern-matched functions

2020-08-27 01:16发布

问题:

Consider the following Haskell code.

data Keypress = Keypress Int Char

getSeq :: Keypress -> [Char]
getSeq (Keypress i c) = replicate i c

Is there any way to write getSeq in pointfree form?

getSeq's definition is so similar to its pattern match that it seems there might be some way to use currying or monads or something to avoid specifying the i and c parameters. However, pointfree.io does not resolve a point-free output for getSeq, I think due to the pattern match.

Is it possible?

回答1:

It is often useful, especially for recursive data types with multiple constructors, to define a catamorphism, a way to fold up a data structure when given one function for each of the possible constructors.

For example, for Bool the catamorphism is

bool :: a -> a -> Bool -> a
bool x _ False = x
bool _ y True = y

and for Either it is

either :: (a -> c) -> (b -> c) -> Either a b -> c
either f g (Left x) = f x
either f g (Right x) = g x

A more advanced catamorphism is the one for lists, which you have probably seen before: foldr!

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f init [] = init
foldr f init (x:xs) = f x (foldr f init xs)

We don't usually think of it this way (or at least I don't), but foldr is a catamorphism: it handles pattern-matching and recursively deconstructing the list for you, so long as you provide "handlers" for values found in the two constructors of [a]:

  • One case to handle [], needing no arguments at all: just a value of type b
  • One case to handle (x:xs). This case takes one argument representing x, the head of the list, and one argument representing the result of folding up the tail recursively, a value of type b.

A catamorphism is less exciting for a type with only one constructor, but we can easily define one for your Keypress type:

key :: (Int -> Char -> a) -> Keypress -> a
key f (Keypress x c) = f x c

In a way, the catamorphism allows you to abstract away the pattern-matching part of the function definition, after which you can just work with functions that don't need to touch the underlying data type directly anymore.

Having defined that generally-useful function once, you can use it many times, to implement any point-free function your heart desires. In your case, you could simply write

getSeq :: Keypress -> [Char]
getSeq = key replicate


回答2:

As written, no. But you can fix that if you want:

data Keypress = Keypress
  { count :: Int
  , char :: Char }

Then

getSeq p = replicate (count p) (char p)

and that can be converted to

getSeq = replicate <$> count <*> char


回答3:

You can’t do it without a little bit of boilerplate, but lens can generate that boilerplate for you, so that’s probably as close as you are going to get.

Using makePrisms from Control.Lens.TH will generate an Iso, which is, essentially, a first-class pattern-match on a single-constructor datatype. Conveniently, Isos are bidirectional, so you can view them (to get values out, like pattern-matching) and review them (to put a value back in, like using the constructor normally).

Using makePrisms and view, it’s possible to write getSeq in a pointfree way:

{-# LANGUAGE TemplateHaskell #-}
import Control.Lens

data Keypress = Keypress Int Char
makePrisms ''Keypress

getSeq :: Keypress -> [Char]
getSeq = uncurry replicate . view _Keypress

Is this better? No idea. The pattern-match in your code looks just fine to me, but if you’re using lens already anyway, this version might be more agreeable to you.



标签: haskell