These are chat archives for got-lambda/expression

18th
Dec 2017
Magnus Therning
@magthe
Dec 18 2017 10:13
@jolod what does the regexp for parsing the input look like?
or rather, the whole function that returns a list of dance moves
jolod
@jolod
Dec 18 2017 10:53
Easiest to look at the code, I think.
jolod
@jolod
Dec 18 2017 11:13
@magthe The input parsing is just ^s(\d+)$, ^x(\d+)\/(\d+)$ and ^p(\D+)\/(\D+)$.
Magnus Therning
@magthe
Dec 18 2017 11:14
yes, those are the regular expressions themselves... but surely there's some code around it handling choice, etc?
jolod
@jolod
Dec 18 2017 11:14
@magthe The spin move is performed by taking the qr/^(.*)()(.{$spin})$/ regexp and using it in s/$re/$3$2$1/.
Magnus Therning
@magthe
Dec 18 2017 11:14
I don't mind having a look at the code, if you have it easily available?
jolod
@jolod
Dec 18 2017 11:15
Partner uses qr/([$p1$p2])(.*)([$p1$p2])/.
@magthe Google for my gists and you'll find it.
Don't want to paste the url here, because gitter inlines it.
Magnus Therning
@magthe
Dec 18 2017 11:20
Private message?
jolod
@jolod
Dec 18 2017 11:28
No longer by the computer.
Magnus Therning
@magthe
Dec 18 2017 14:09
My parser using Text.ParserCombinators.ReadP isn't much longer than your regexp-based parser.
Magnus Therning
@magthe
Dec 18 2017 14:16
Of course it's highly subjective as to which is more readable/maintainable/...
Marco Zocca
@ocramz
Dec 18 2017 14:52
erm, shots fired ..
jolod
@jolod
Dec 18 2017 14:52
@magthe Is the code available anywhere?
Magnus Therning
@magthe
Dec 18 2017 14:53
I'll paste it here. It's just the parser so not too revealing I'd say.
Marco Zocca
@ocramz
Dec 18 2017 14:53
OT: I'm in contact with a researcher in the Claessen group at Chalmers for a talk next year: these are the candidate topics, in his own words:
Max should hopefully appear on this chat in the near future as well
Magnus Therning
@magthe
Dec 18 2017 14:55
data Move = Spin Int
          | Exchange Int Int
          | Partner Int Int
          deriving (Show)

readMove = choice [readSpin, readExchange, readPartner]
  where
    readSpin = Spin <$> (char 's' *> readS_to_P reads)
    readExchange = Exchange <$> (char 'x' *> readS_to_P reads) <*> (char '/' *> readS_to_P reads)
    readPartner = Partner <$> (char 'p' *> readS_to_P reads) <*> (char '/' *> readS_to_P reads)
Marco Zocca
@ocramz
Dec 18 2017 14:55
readP is in base also
very handy
Magnus Therning
@magthe
Dec 18 2017 14:56
Then the Read instansce is declared as
instance Read Move where
  readPrec = R.lift readMove
  readListPrec = R.lift $ sepBy readMove (char ',')
Yupp, @ocramz , that's why I chose to use it... I was too lazy to set up a full stack environment ;)
(the R.lift there is Text.Read.lift.)
Marco Zocca
@ocramz
Dec 18 2017 14:57
And by coincidence, readP was initially written by that same Claesse
n
@Jell what do you think of a meetup after the AoC one in late January?
Magnus Therning
@magthe
Dec 18 2017 15:00
@ocramz QuickSpec :+1:
Marco Zocca
@ocramz
Dec 18 2017 15:01
Göteborg is QuickCheck city yo
jolod
@jolod
Dec 18 2017 15:01
@magthe Yeah. I guess it's really subjective... I find those really not glancable, but I parse m<^x(\d)/(\d)$> very easily.
@magthe Where does readS_to_P come from, and what does it do?
jolod
@jolod
Dec 18 2017 15:03
Does it represent reading any char?
@magthe How do you then write the patterns and use them with the substitution, that performs the dance?
Magnus Therning
@magthe
Dec 18 2017 15:06
@jolod and I find stuff like m<... everything but glancable... and isn't \d a single digit, so \d+ would be needed?
jolod
@jolod
Dec 18 2017 15:06
Yeah, mistyped.
Magnus Therning
@magthe
Dec 18 2017 15:07
@jolod I do like you did, I fold
jolod
@jolod
Dec 18 2017 15:07
@magthe Can you paste your Move -> String -> String function?
Magnus Therning
@magthe
Dec 18 2017 15:08
@jolod I don't have one
jolod
@jolod
Dec 18 2017 15:08
?
Magnus Therning
@magthe
Dec 18 2017 15:09
I haven't solved the problem... I've only written a parser for the input.
jolod
@jolod
Dec 18 2017 15:09
Yeah, but that's not where regexes really come in to my solution. That's just the parse step. I then use regexes to perform the dance.
Magnus Therning
@magthe
Dec 18 2017 15:09
So, s/I do/I would do/, above :)

Yes, I know, but your comment from above was:

First I of course use it for parsing the input. A proper parser would be rather overkill, I think. And other manual string parsing would just be emulating a regex.

That was the only part that I was really interested in... as I don't think a "proper parser" is overkill ;)
Then I agree that returning a list of regexps from your parser, and folding over them is a neat trick.
jolod
@jolod
Dec 18 2017 15:14
For me, needing to write a type class instance, and defining a data structure, and then also write the actual specification for what you want to parse, is a bit overkill, compared to a single function.
But YMMV.
Magnus Therning
@magthe
Dec 18 2017 15:17
I don't need the type class instance (Read) it's just handy because ReadP has a slightly silly API for actually running parsers.
And, @jolod, would you really not define a data structure if you were to solve it in Haskell?
jolod
@jolod
Dec 18 2017 15:19
I'd do as I did in Perl. Just have it return a function String -> String. It's all I care about. Why introduce another step when all you do then is to define three functions (probably named the same in Haskell) that turn the different cases into String -> String functions?
Or a Pattern, as it were in Perl.
But in Haskell I'd go for a function.
so type Step = String -> String and I'd have String -> List Step where the string is the input. I would have no need for an intermediate data representation.
One thing I wasn't happy about in the Perl version was that I decoupled the pattern and it's captures from the substitution, which makes use of the captures.
Magnus Therning
@magthe
Dec 18 2017 15:23
Yes, I like the idea of having the parser return a function and then fold using $
Magnus Therning
@magthe
Dec 18 2017 15:37

So, something like this then:

spinList :: Int -> String -> String
spinList n xs = undefined

exchangeElementsAt :: Int -> Int -> String -> String
exchangeElementsAt = undefined

swapElements :: Char -> Char -> String -> String
swapElements = undefined

readSpin = spinList <$> (char 's' *> readS_to_P reads)
readExchange = exchangeElementsAt <$> (char 'x' *> readS_to_P reads) <*> (char '/' *> readS_to_P reads)
readPartner = swapElements <$> (char 'p' *> get) <*> (char '/' *> get)

And then it's reduced to writing three functions String -> String.

But again, the parser isn't very complicated at all... I think (YMMV, of course)
Magnus Therning
@magthe
Dec 18 2017 15:42
(IMO a good reason to have an intermediate representation is that there's no Show for [String -> String].)
jolod
@jolod
Dec 18 2017 15:43
Just zip it up with the string you got it from.
Then throw away the string when you don't need it.
... #frugal
@magthe Can you show the context where these are used? Like a function with type [String] -> [String -> String].
jolod
@jolod
Dec 18 2017 15:50
@magthe Can you explain how readS_to_P works? I guess it reads to a Nothing if it cannot read anything that matches an Int?
Magnus Therning
@magthe
Dec 18 2017 15:55
readS_to_P reads has type Read a => ReadP a, i.e. it reads anything that has a Read instance, wrapped up in the parser type ReadP.
jolod
@jolod
Dec 18 2017 15:56
And how do you get from that to an int or a char?
Oh, i see. you use get to get the char.
So how do you get an Int from readS_to_P?
Magnus Therning
@magthe
Dec 18 2017 15:57
That's how typeclasses work!
jolod
@jolod
Dec 18 2017 15:57
Obviously, but where is it defined?
Magnus Therning
@magthe
Dec 18 2017 15:58
Read is defined on Int by the system... also for Char (so using get is a shortcut)
jolod
@jolod
Dec 18 2017 15:59
^^ this, btw, is the biggest benefit of parsers IMO.
(Compared to when a regex would also work.)
You get the type. Somethings your must matching strings, and then it's no benefit, but as soon as you're extracting numerical values it's really nice.
Magnus Therning
@magthe
Dec 18 2017 16:02

Anyway, here's the definition for the function String -> [String -> String]:

fst . last . readP_to_S readMoves

(as I said, the API for ReadP is not that good, but it's in the standard lib.)

The function String -> String could then be foldr ($) ['a' .. 'p'] . fst . last . readP_to_S readMoves (modulo possible need of reversing stuff, or something).
jolod
@jolod
Dec 18 2017 16:17
@magthe Can't you please make a full Haskell solution to the puzzle? I'm writing a PS port of my Perl solution as a comparision, and would love to have your solution as another reference point.
Magnus Therning
@magthe
Dec 18 2017 16:18
@jolod did you have to ask so nicely? ;)
Magnus Therning
@magthe
Dec 18 2017 16:58
@jolod done, though I've only tested it on the simple example in the problem statement
it's 30 lines of code, do you want it here or somewhere else?
jolod
@jolod
Dec 18 2017 16:59
A gist is good.
Magnus Therning
@magthe
Dec 18 2017 17:03
It's here: https://gist.github.com/magthe/ 3388140dfd59ff49d573971194bc39d3
The latest one, Part1.hs.
jolod
@jolod
Dec 18 2017 17:04
My PS version failed because JS RegExp apparently doesn't support (?<=) :-(.
Lookbehinds are so useful...
I can fix it, but ... bummer ...
jolod
@jolod
Dec 18 2017 17:15
I think @magthe has convinced me that for just parsing it's cleaner to use a parser in a Haskell-like. Undecided on substitutions though.
Perhaps the API need to be tweaked a bit though.
Magnus Therning
@magthe
Dec 18 2017 17:16
:muscle: :)
The API for the ReadP parser? Oh yes, absolutely. Luckily there are other parser libraries out there :)
jolod
@jolod
Dec 18 2017 17:17
Simple stuff like the things you do with regexes usually, imo, do not benefit from being verbose or "readable" as in English. Rather, there's a point in being terse. Just like a piece of FP code usually fit on a couple of lines whereas some other mainstream languages would require a page.
Veit Heller
@hellerve
Dec 18 2017 17:18
it’s kind of a bummer that we don’t have any lex/yacc lovers here. that would make these discussions even more interesting
if i had to type out a haskell parser combinator everytime i refactor code i’d go crazy; they definitely have their place
jolod
@jolod
Dec 18 2017 17:19
Being able to read the pattern in chunks makes it faster to comprehend. This, of course, depends on you being literate in the RE language.
@magthe How about back references? This instance didn't need that, but I fairly often use back references.
I guess you'd have something equivalent to do a <- capture digit; any; backref a.
Such an interface would be pretty nice; for large regexes in Perl you use the /x modifier which ignores whitespace so that you can layout the pattern over several lines; it would be quite similar to a do version.
Magnus Therning
@magthe
Dec 18 2017 17:22
There's usually a combinator String -> Parser String that expects to find the provided String... would that do?
jolod
@jolod
Dec 18 2017 17:23
Yeah. But how do you get the string to match?
Magnus Therning
@magthe
Dec 18 2017 17:23
For a Char in ReadP you'd do do c <- get; <some other parsing>; char c
jolod
@jolod
Dec 18 2017 17:24
Nice.
Oh, and here's the second benefit to parsers. You can transform the back reference. So you can write patterns that match <...> or [...] or {...}.
Magnus Therning
@magthe
Dec 18 2017 17:25
And something similar for String... and if you parsed a digit/number you can use show
jolod
@jolod
Dec 18 2017 17:25
That's not something you can do with a re.
Magnus Therning
@magthe
Dec 18 2017 17:26
or just parse the second, compare, and fail if they aren't equal
jolod
@jolod
Dec 18 2017 17:26
:-/ That makes me less happy.
I'd go with show.
Magnus Therning
@magthe
Dec 18 2017 17:27
Well, I'm sure you can create your own combinators eaily too :)
jolod
@jolod
Dec 18 2017 17:27
Assuming that it actually does show exactly the same.
I wonder how that would work for floats with too many digits.
So actually I think I would want to have the parser return the matched string and the value.
so (s, i) <- parseInt.
Then you can choose if you want to match exactly the same string, or match the same value.
@magthe But as I said, I don't find libraries such as http://search.cpan.org/~chromatic/Regexp-English-1.01/lib/Regexp/English.pm an improvement.
jolod
@jolod
Dec 18 2017 17:32
I would still think it would be really nice to have compiler support for regexes, which would be turned into a data representation which can then be turned into your parser of choice through a library.
I get the objection that it's a DSL that you need to learn, but I don't really buy it, because there's a lot of DSLs in e.g. Haskell. Why would RE be any different?
The argument is rather in the other direction. RE's are not a Haskell-specific DSL and be be used in many different contexts, including your code editor (I hope!).
Jean-Louis Giordano
@Jell
Dec 18 2017 17:41
@ocramz I'm running out of steam for organizing meetups :p so I think if we do another meetup let january we need to find some other hosts
Magnus Therning
@magthe
Dec 18 2017 17:43
RE is all about string manipulation. It fits well in Perl, because its very raison d'etre is string manipulation.
Magnus Therning
@magthe
Dec 18 2017 17:51
jolod
@jolod
Dec 18 2017 19:56
Again, I'm not saying that parser aren't useful. I think I've been pretty clear about that.
Magnus Therning
@magthe
Dec 18 2017 19:58
Yes, you have.
Magnus Therning
@magthe
Dec 18 2017 20:05
It wasn't meant to imply that you ever said that... it was only meant to show that parsers can be used for other things than parsing text.
Maximilian Algehed
@MaximilianAlgehed
Dec 18 2017 21:09
@ocramz Asked me if I wanted to give a talk at the next meetup. When someone with the ability decides to organise it, please ping me at algehed@chalmers.se
jolod
@jolod
Dec 18 2017 21:18
@magthe And RE's can parse other things than text, such as data structures. See https://clojure.org/about/spec. ;-)
OK, so maybe that's stretching the definition a bit. :-)
jolod
@jolod
Dec 18 2017 21:29
@magthe It looks like "your" parser, handing it off to a data structure, would be really quite useful in today's AoC. :-)
Marco Zocca
@ocramz
Dec 18 2017 21:30
thx for dropping by @MaximilianAlgehed , yeah we'll make it happen somehow
I'll start lobbying my own conpany aa well
Magnus Therning
@magthe
Dec 18 2017 23:11
Well, I'm sure RE could be used for more than matching text, but I've never seen an API for it.
@jolod have you?
Maximilian Algehed
@MaximilianAlgehed
Dec 18 2017 23:24
process algebras are (sometimes) regular languages, no?
Magnus Therning
@magthe
Dec 18 2017 23:36
Good question!
Magnus Therning
@magthe
Dec 18 2017 23:42
Though I should probably have written that I've never come across an RE engine that allows patterns matching anything other than text. While I have seen parser libs that do (e.g. parsec)
Maximilian Algehed
@MaximilianAlgehed
Dec 18 2017 23:45
I'm not sure I have any concrete counterexample in mind, but if I think of anything I'll try to let you know
jolod
@jolod
Dec 18 2017 23:46
@magthe Yeah, I think regular expression usually refers to a "text syntax" for matching against strings, in contrast to regular language.
Maximilian Algehed
@MaximilianAlgehed
Dec 18 2017 23:46
on the topic of process algebra I think it's the case that standard Milner style process algebras with ||, +, and ! can be seen as regular languages after some reading...
jolod
@jolod
Dec 18 2017 23:47
I don't know how to respond to such a statement ... :-)
Maximilian Algehed
@MaximilianAlgehed
Dec 18 2017 23:48
:P
Magnus Therning
@magthe
Dec 18 2017 23:50
According to Wikipedia a regular language is a language that can be expressed using a regular expression (https://en.m.wikipedia.org/wiki/Regular_language)
Maximilian Algehed
@MaximilianAlgehed
Dec 18 2017 23:50
I'll make the stronger statement: Some process algebras are regular languages
yes
jolod
@jolod
Dec 18 2017 23:51
It just occurred to me that the language of regular expression is not regular.
At least if you have capturing.
Magnus Therning
@magthe
Dec 18 2017 23:52
Well, a regular expression pattern doesn't have capturing
jolod
@jolod
Dec 18 2017 23:52
@magthe Most RE engines do... So should have said PCRE or something like that.
Magnus Therning
@magthe
Dec 18 2017 23:53
Yes, the RE engines usually implement something that is more expressive than regular expressions
jolod
@jolod
Dec 18 2017 23:55
A RE engine without capturing would be ... let's say "less useful".
Magnus Therning
@magthe
Dec 18 2017 23:55
Indeed!
Even "less than useful"
jolod
@jolod
Dec 18 2017 23:56
I can see a use case for input data validation.
And that's really all you need, because if you need more you have parsers! #amirite
Magnus Therning
@magthe
Dec 18 2017 23:57
😜