CODEWITHSUNDEEP
haskelltransformation
Jeff
Jeff

Reputation: 263

Haskell: Simplifying Functions Through "Principled Transformations"

This past week or two in my computer science class, we've been asked show how functions can be simplified and shortened through "principled transformations." We have not been receiving feedback on these assignments so I have no idea if I'm doing it right.

Here's my latest exercise, and my attempt at a solution:

Show by a series of principled transformations that we can define:
    char :: Char -> Parser Char
    char c = satisfy (c==)
as
    char :: Char -> Parser Char
    char = satisfy . (==)

My attempt:

char c = satisfy (c==)
=> char c = satisfy . c==
=> char c = satisfy . flip ==c
=> char = satisfy . flip ==
=> char = satisfy . (==)

Could I get some feedback please? The code provided for the assignment is incomplete, so I cannot compile it and test to see if each transformation works. I tried writing a similar set of functions to test the transformations myself, but I unfortunately am very bad at and new to Haskell so I couldn't figure that out either.

Upvotes: 2

Views: 259

Answers (2)

daniel gratzer
daniel gratzer

Reputation: 53881

Well there are a few errors here, first I'm going to write down relevant types

char :: Char -> Parser Char
satisfy :: (Char -> Bool) -> Parser Char
(==) :: Char -> Char -> Char

I've deliberately restricted some signatures to make this more pleasant.

char c = satisfy (c==)
char c = satisfy . c== -- This is a parse error, not sure what you meant
char c = satisfy . flip ==c -- Also wrong, flip swaps arguments, 
                            -- but this function has only one argument
char = satisfy . flip == -- Eta conversion is right, this code is
                         -- still a parse error - you should check code with ghci or winhugs

My approach would be

char c = satisfy   (c==)
char c = satisfy $ (\c -> \d -> c == d) c -- Explicitly undo sections
char c = satisfy . (\c d -> c == d) $ c -- f(g x) === (f . g) x by the
                                        -- definition of composition
char c = (satisfy . (==)) c
char = satisfy . (==)

Upvotes: 3

Sarah
Sarah

Reputation: 6695

Here's a step-by-step approach:

char c = satisfy (c==)
char c = satisfy (\x -> c == x)   -- Sections [1]
char c = satisfy (\x -> (==) c x) -- Prefix form
char c = satisfy ((==) c)         -- Eta reduction [2]
char c = (.) satisfy (==) c       -- Composition: `(.) f g x = f (g x)`
char c = (satisfy . (==)) c       -- Infix form
char   = satisfy . (==)           -- Eta reduction

I would maybe even forgo explicitly expanding the section and simply go from (c==) to ((==) c).

1: http://www.haskell.org/onlinereport/haskell2010/haskellch3.html#x8-300003.5
2: http://www.haskell.org/haskellwiki/Eta_conversion

Upvotes: 8

Related Questions