Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. short function to remove and replace an item (Michael P Mossey)
2. Re: short function to remove and replace an item (Vlad Skvortsov)
3. Re: short function to remove and replace an item (Daniel Fischer)
4. Re: short function to remove and replace an item (Zachary Turner)
5. Re: short function to remove and replace an item (Zachary Turner)
6. Re: making translation from imperative code (Heinrich Apfelmus)
7. Can we make this program better (and shorter)? (Zachary Turner)
----------------------------------------------------------------------
Message: 1
Date: Wed, 01 Apr 2009 17:45:29 -0700
From: Michael P Mossey <[email protected]>
Subject: [Haskell-beginners] short function to remove and replace an
item
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
What if I have a list xs, and I want to remove one item and replace it
with another? The item to remove can be detected by a predicate
function. The order of the items doesn't matter. How about this:
replaceItem :: (a -> Bool) -> a -> [a] -> [a]
replaceItem p new xs = new : snd (partition p xs)
This will actually replace all items that match the predicate with one
copy of 'new'. It will also prepend 'new' even if no items match the
predicate.
For another challenge, can someone explain to me how to write this in
point-free style?
Thanks,
Mike
------------------------------
Message: 2
Date: Wed, 01 Apr 2009 18:01:55 -0700
From: Vlad Skvortsov <[email protected]>
Subject: Re: [Haskell-beginners] short function to remove and replace
an item
To: Michael P Mossey <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Prelude> let replaceItem p n = map (\x -> if p x then n else x)
Prelude> replaceItem odd 100 [1..10]
[100,2,100,4,100,6,100,8,100,10]
Michael P Mossey wrote:
> What if I have a list xs, and I want to remove one item and replace it
> with another? The item to remove can be detected by a predicate
> function. The order of the items doesn't matter. How about this:
>
> replaceItem :: (a -> Bool) -> a -> [a] -> [a]
> replaceItem p new xs = new : snd (partition p xs)
>
> This will actually replace all items that match the predicate with one
> copy of 'new'. It will also prepend 'new' even if no items match the
> predicate.
>
> For another challenge, can someone explain to me how to write this in
> point-free style?
--
Vlad Skvortsov, [email protected], http://vss.73rus.com
------------------------------
Message: 3
Date: Thu, 2 Apr 2009 03:38:40 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] short function to remove and replace
an item
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Donnerstag 02 April 2009 02:45:29 schrieb Michael P Mossey:
> What if I have a list xs, and I want to remove one item and replace it
> with another? The item to remove can be detected by a predicate
> function. The order of the items doesn't matter. How about this:
>From the description, I'd rather have expected something like
replaceItem :: (a -> Bool) -> a -> [a] -> [a]
replaceItem p new (x:xs)
| p x = new : xs -- or new : replaceItem p new xs
| otherwise = x : replaceItem p new xs
replaceItem _ _ [] = []
which could also be nicely written as
replaceItem p new xs =
case break p xs of
(front,_:back) -> front ++ new : back
_ -> xs
the multiple replace: map (\x -> if p x then new else x) xs
>
> replaceItem :: (a -> Bool) -> a -> [a] -> [a]
> replaceItem p new xs = new : snd (partition p xs)
This could also be written as
replaceItem p new xs = new : filter (not . p) xs
>
> This will actually replace all items that match the predicate with one
> copy of 'new'. It will also prepend 'new' even if no items match the
> predicate.
>
> For another challenge, can someone explain to me how to write this in
> point-free style?
replaceItem p new xs = new : snd (partition p xs)
rewrite the right hand side as
(new :) . snd . (partition p) $ xs
Now you can drop the last argument (xs)
replaceItem p new = (new :) . snd . partition p
To move new to the end, rewrite the right hand side as
((:) new) . (snd . partition p)
=== (. (snd . partition p)) . (:) $ new
Now you can drop the next parameter, new:
replaceItem p = (. (snd . partition p)) . (:)
To move the predicate p to the end, rewrite the right hand side as
(.) (. (snd . partition p)) (:)
=== flip (.) (:) (. (snd . partition p))
=== flip (.) (:) $ flip (.) (snd . partition p)
=== flip (.) (:) $ flip (.) ((snd .) . partition $ p)
=== flip (.) (:) . flip (.) $ ((snd .) . partition $ p)
=== flip (.) (:) . flip (.) . (snd .) . partition $ p
Now you can drop the last parameter, p:
replaceItem = flip (.) (:) . flip (.) . (.) snd . partition
Prelude Data.List> let replaceItem = flip (.) (:) . flip (.) . (.) snd .
partition in
replaceItem even 7 [1 .. 20]
[7,1,3,5,7,9,11,13,15,17,19]
But please, don't write your code in that style. Getting rid of xs is fine,
dropping
new leads to hard to read code. Removing all arguments is sheer obfuscation.
There's more to writing pointfree code than being able to, one must also know
when to stop.
>
> Thanks,
> Mike
Cheers,
Daniel
------------------------------
Message: 4
Date: Wed, 1 Apr 2009 21:50:04 -0500
From: Zachary Turner <[email protected]>
Subject: Re: [Haskell-beginners] short function to remove and replace
an item
To: Michael P Mossey <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Wed, Apr 1, 2009 at 7:45 PM, Michael P Mossey <[email protected]>wrote:
> What if I have a list xs, and I want to remove one item and replace it with
> another? The item to remove can be detected by a predicate function. The
> order of the items doesn't matter. How about this:
>
> replaceItem :: (a -> Bool) -> a -> [a] -> [a]
> replaceItem p new xs = new : snd (partition p xs)
>
> This will actually replace all items that match the predicate with one copy
> of 'new'. It will also prepend 'new' even if no items match the predicate.
>
> For another challenge, can someone explain to me how to write this in
> point-free style?
>
I used an intermediate helper function, but the replaceItem function is
point free
choose :: (a -> Bool) -> (a -> b) -> (a -> b) -> a -> b
choose pred yes _ val | (pred val) = yes val
choose _ _ no val = no val
replaceItem :: (a -> Bool) -> a -> [a] -> [a]
replaceItem pred rep = map (choose pred id (const rep))
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090401/aa44421e/attachment-0001.htm
------------------------------
Message: 5
Date: Wed, 1 Apr 2009 22:03:09 -0500
From: Zachary Turner <[email protected]>
Subject: Re: [Haskell-beginners] short function to remove and replace
an item
To: Michael P Mossey <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Wed, Apr 1, 2009 at 9:50 PM, Zachary Turner <[email protected]>wrote:
>
>
> On Wed, Apr 1, 2009 at 7:45 PM, Michael P Mossey
> <[email protected]>wrote:
>
>> What if I have a list xs, and I want to remove one item and replace it
>> with another? The item to remove can be detected by a predicate function.
>> The order of the items doesn't matter. How about this:
>>
>> replaceItem :: (a -> Bool) -> a -> [a] -> [a]
>> replaceItem p new xs = new : snd (partition p xs)
>>
>> This will actually replace all items that match the predicate with one
>> copy of 'new'. It will also prepend 'new' even if no items match the
>> predicate.
>>
>> For another challenge, can someone explain to me how to write this in
>> point-free style?
>>
>
> I used an intermediate helper function, but the replaceItem function is
> point free
>
> choose :: (a -> Bool) -> (a -> b) -> (a -> b) -> a -> b
> choose pred yes _ val | (pred val) = yes val
> choose _ _ no val = no val
>
> replaceItem :: (a -> Bool) -> a -> [a] -> [a]
> replaceItem pred rep = map (choose pred id (const rep))
>
Ok I looked at the OP again and apparently I didn't understand the wording
of the question :P I just thought it said to replace each element in the
list that matched the predicate with the new item.
How about this?
replaceItem :: [a] -> (a -> Bool) -> a -> [a]
let replaceItem xs pred = (: filter (not.pred) xs)
Note that I changed the order of the arguments, the value now comes last.
But I think this still should be ok?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090401/fec35904/attachment-0001.htm
------------------------------
Message: 6
Date: Thu, 02 Apr 2009 07:30:27 +0200
From: Heinrich Apfelmus <[email protected]>
Subject: [Haskell-beginners] Re: making translation from imperative
code
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Michael Mossey wrote:
> Heinrich Apfelmus wrote:
>>
>> Can you elaborate on what exactly the algorithm is doing? Does it just
>> emit notes/chords/symbols at given positions or does it also try to
>> arrange them nicely? And most importantly, "where" does it emit them to,
>> i.e. what's the resulting data structure?
>>
>> So far, the problem looks like a basic fold to me.
>
> Here is some Haskell code that explains the problem in
> more detail.
> [...]
Thanks for the elaboration.
I think the code doesn't separate concerns very well; mixing information
about widths and times, page size and the recursion itself into one big
gnarl.
Also, there is one important issue, namely returning a special value
like -1 as error code in
> tryAgain state =
> case scoreNextTime score (time state) of
> -1 -> indicateNoMoreChunks state
> t -> layoutSystem' (setTime state t)
Don't do this, use Maybe instead
tryAgain state = case scoreNextTime score (time state) of
Nothing -> indicateNoMoreChunks state
Just t -> layoutSystem' (state { time = t })
where Nothing indicates failure and Just success.
Back to the gnarl in general, I still don't have a good grasp on the
problem domain, which is key to structuring the algorithm. Therefore,
I'll expand on toy model and you tell me how it differs from the real thing.
The model is this: we are given several lists of notes (f.i. a piano
part and a vocal line) where each note is annotated with the time it is
to be played at. We abstract away the fact that we are dealing with
musical notes and simply consider a list of *events*
type Time = Integer
type Events a = [(Time, a)]
with the invariant that the timestamps are (strictly) increasing:
valid :: Events a -> Bool
valid xs = all $ zipWith (\(t1,_) (t2,_) -> t1 < t2) xs (drop 1 xs)
Now, the toy task is to merge several lists of similar events into one
big list that is ordered by time as well.
merge :: [Events a] -> Events [a]
Since some events may now occur simultaneously, the events of the
results are actually lists of "primitive" events.
One possibility for implementing merge is to start with a function to
merge two event lists
merge2 :: Events [a] -> Events [a] -> Events [a]
merge2 [] ys = ys
merge2 xs [] = xs
merge2 xs@((tx,x):xt) ys@((ty,y):yt) = case compare tx ty of
LT -> (tx,x ) : merge2 xt ys
EQ -> (tx,x++y) : merge2 xt yt
GT -> (ty, y) : merge2 xs yt
and to apply it several times
merge = foldr merge2 [] . map lift
where lift = map $ \(t,x) -> (t,[x])
Another possibility is to simply concatenate everything first and then
sort by time
merge = map (\((t,x):xs) -> (t,x:map snd xs))
. groupBy ((==) `on` fst)
. sortBy (comparing fst)
. concat
The code above can be made more readable by choosing nice names like
time = fst
event = snd
or avoiding pairs altogether and implementing these names as record
fields. Also, the (&&&) combinator from Control.Arrow is very handy.
merge = map (time . head &&& map event)
. groupBy ((==) `on` time)
. sortBy (comparing time)
. concat
I hope this gives you a few ideas to think about. How does this toy
model differ from the real thing?
Regards,
apfelmus
PS: If some parts of my example code give you trouble, it's probably
fastest to ask around on the #haskell IRC channel.
--
http://apfelmus.nfshost.com
------------------------------
Message: 7
Date: Thu, 2 Apr 2009 01:34:04 -0500
From: Zachary Turner <[email protected]>
Subject: [Haskell-beginners] Can we make this program better (and
shorter)?
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-7"
Be warned, this code is really ugly. I need some help to make it better.
I was in this situation this week where there was a sample of some numbers.
I knew the valid possible range that numbers could lie in, and I knew about
30% of the actual values from the sample. I also knew the original average
and the original standard deviation. I wanted more information about the
other values in the sample, so I sat down and derived two formulas: One
that, given an average, the number of items in the average, and 1 number
that you know was used somewhere in the calculation of the average,
calculates what the average would be if that number had not been there.
Another that does the same for standard deviation. The second formula is
fairly insane, if someone can figure out how to simplify it let me know, it
took forever to derive it without making any mistakes. Actually I didn't
even know it was possible to do a running standard deviation like that until
I sat down and derived it.
So anyway the program asks the user how large the original sample was, and
the average and standard deviation. Then it runs in a loop asking it for a
value to remove from the sample set and calculate the updated values. For
certain values however, even if they are actually in the range of valid
values for the range of the sample space, they might be impossible to
achieve given a certain sample size, average, and stdev (for example, if you
have two numbers in the range [0..100] and the average is 100, and you
remove 1 number, none of the remaining numbers can be 0 obviously). So I
wanted to detect this if the user inputs such a value, that way for one
thing I can calculate exact upper and lower bounds for the actual range of
the numbers just by trying all possible values.
I know that the nature of the program mandates that there's going to be a
lot of IO Monadic code, but I still feel like my code sucks.
For one thing, I really tried to make the removePoints method be pure, and
just accept a list as the argument and do the I/O in another function. I
imagined some kind of lazy list comprehension, where each time the
removePoints method asked for the next item, it would ask for the input and
do all that stuff. I couldn't figure out how to make this work. Perhaps
it's not even possible, since by definition a list comprehension that asked
for input when forced isn't pure. But I still think there's a better way to
do it.
I also really dislike having to do manual recursion for getting input,
there's got to be a way to use lists and built-in functions to do it for
you, using some kind of takeWhile() perhaps.
Anyway if anyone has any suggestions for making this code look better, more
elegant, or more Haskelly, let me know :)
import Control.Arrow
promptUntilValid :: (Read a, Show a, Eq a) => String -> IO a
promptUntilValid prompt = do
putStr prompt
putStr " "
result <- getLine
case (reads result) of
[(parsed,_)] -> return parsed
invalid -> do
putStrLn $ "Invalid input! You entered " ++ result ++ ", and
results length is " ++ (show (length invalid))
promptUntilValid prompt
newStdev :: Int -> (Int,Int,Double,Double,Double) -> Double
newStdev removeValue (old_count, new_count, old_stdev, old_avg, new_avg) =
sqrt.(/ (n-1.0)) $
n * ó_x^2 + 2.0*old_avg*new_avg*(n-1.0) - (n-1.0)*old_avg^2 - (a_n -
old_avg)^2 - (n-1.0)*new_avg^2
where
ó_x = old_stdev
n = fromIntegral old_count
a_n = fromIntegral removeValue
removeSinglePoint :: Int -> (Int,Double,Double) -> (Int,Double,Double)
removeSinglePoint value (count,stdev,avg) =
(new_count,new_stdev,new_avg)
where new_count = count-1
new_avg = (avg*(fromIntegral count) - (fromIntegral value)) /
(fromIntegral new_count)
new_stdev = newStdev value (count, new_count, stdev, avg, new_avg)
removePoints :: (Int,Double,Double) -> IO ()
removePoints (count,stdev,avg) = do
putStr "Enter a number to remove from the sample set (Enter to stop): "
putStr " "
result <- getLine
case (result,reads result) of
("",_) -> return ()
(_, [(parsed,_)]) -> do
if (any (uncurry (||) . (isInfinite &&& isNaN)) [new_stdev,
new_avg])
then do
putStrLn "That number could not have been there! The new
values are NaN!"
removePoints (count,stdev,avg)
else do
putStrLn $ "New count: " ++ (show new_count) ++ ", new
stdev: " ++ (show new_stdev) ++ ", new avg: " ++ (show new_avg)
removePoints (new_count,new_stdev,new_avg)
where (new_count,new_stdev,new_avg) = removeSinglePoint parsed
(count,stdev,avg)
(_,invalid) -> do
putStrLn $ "Invalid input! You entered " ++ result ++ ", and
results length is " ++ (show (length invalid))
removePoints (count,stdev,avg)
main = do
num_values::Int <- promptUntilValid "Enter the initial number of values:
"
stdev::Double <- promptUntilValid "Enter the initial standard deviation:
"
average::Double <- promptUntilValid "Enter the initial average: "
putStrLn ("num_values = " ++ (show num_values))
putStrLn ("stdev = " ++ (show stdev))
putStrLn ("average = " ++ (show average))
removePoints (num_values, stdev, average)
return ()
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090402/2f361ee4/attachment.htm
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 10, Issue 2
****************************************
