Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Toy Problem of the Week

Name: Anonymous 2009-12-12 18:22

I was raking around on the net and found this problem and coded up a solution. Once we get at least 10 solutions I'll post mine and a link to where I found the problem.
Any language, any libraries (but declare them) allowed. Aim for clarity and conciseness. Assume the input is well formed. Mine is 5 lines of scheme code (6 if we include requiring a library). No calling an "answer" function that "you wrote already and put in an external lib" ;)

Consider the problem of turning a list consisting
of a mix between symbols and non-symbols into a
list of lists of the symbol and its following
non-symbols. That is:

Input:    ({<symbol> <non-symbol>*} ... )
Output:   ((<symbol> (<non-symbol>*)) ...)
Example:     (a 1 2 3 b 4 5 c d 8 9 e)
           -> ((a (1 2 3)) (b (4 5)) (c ()) (d (8 9)) (e ()))

Name: Anonymous 2009-12-13 1:09

One line of actual code does the job:

import Data.List (groupBy)

f :: (String -> Bool) -> [String] -> [[String]]
f isSymbol = groupBy (const $ not . isSymbol)


Given a predicate that determines whether a string is a symbol or not, ``f'' produces the desired function.

Example:

GHCi> -- We define a symbol to be a string that does not begin with a digit.
GHCi> -- For the sake of simplicity, all strings are assumed to be non-empty.
GHCi> let isSymbol = (`notElem` ['0'..'9']) . head
GHCi> -- Let's test it.
GHCi> (isSymbol "foo", isSymbol "3bar")
(True,False)
GHCi> -- Finally, we test f.
GHCi> f isSymbol ["a", "1", "2", "3", "b", "4", "5", "c", "d", "8", "9", "e"]
[["a","1","2","3"],["b","4","5"],["c"],["d","8","9"],["e"]]


Now, due to the fact that Haskell's lists are homogenous, the output format is slightly different from the one specified in >>1. We can alter f to return tuples instead:

f :: (String -> Bool) -> [String] -> [(String, [String])]
f isSymbol = map (\ (s : ns) -> (s, ns)) . groupBy (const $ not . isSymbol)


And we get:

GHCi> f isSymbol ["a", "1", "2", "3", "b", "4", "5", "c", "d", "8", "9", "e"]
[("a",["1","2","3"]),("b",["4","5"]),("c",[]),("d",["8","9"]),("e",[])]

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List