Difference between pages "User talk:Atravers" and "99 questions/Solutions/10"
m (Improved grammar) |
m (fix omission of function "group" in offered alternate list comprehension) |
||
Line 1: | Line 1: | ||
+ | (*) Run-length encoding of a list. |
||
− | === Thank You, Atravers! === |
||
− | I appreciate all your work on the wiki. Carry on! Please let me know if I can help in any way. —[[User:HowardBGolden|HowardBGolden]] ([[User talk:HowardBGolden|talk]]) 20:46, 14 March 2021 (UTC) |
||
+ | Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E. |
||
− | Thanks (I assume you're referring to what I've rewritten, rather than what I've wrote myself ;-). Considering just how much content is here, I didn't think I was making ''that'' much of a difference.<br> |
||
− | I do have a question: has anyone [else] expressed an interest in using CommonMark here? |
||
− | * I frequently type out CM formatting at first, only to then replace it with what the HsWiki uses now; |
||
− | * Of course, if MediaWiki is already switching to CM, then the question is academic... |
||
− | — [[User:Atravers|Atravers]] 12:37 15 March 2021 (UTC) |
||
+ | <haskell> |
||
− | :''(Note: Above reply from Atravers seems to have an incorrect timestamp) — s/b 15 March 2021 (UTC)'' |
||
+ | encode xs = map (\x -> (length x,head x)) (group xs) |
||
− | :I don't recall anyone expressing an interest in using CommonMark. However, we haven't really solicited suggestions, so this isn't much indication of interest level. |
||
+ | </haskell> |
||
− | :At the moment, you might want to use [https://pandoc.org Pandoc] on your own computer to convert your CommonMark to MediaWiki and then paste it into wiki pages. Perhaps we can even set up a converter app on our server to do this. — [[User:HowardBGolden|HowardBGolden]] ([[User talk:HowardBGolden|talk]]) 18:02, 15 March 2021 (UTC) |
||
+ | which can also be expressed as a list comprehension: |
||
− | :''(Time corrected, again - problem with client, not HsWiki server >_< )'' |
||
− | :Heh - I must be one of the few still doing this "directly" (no intervening tools like Pandoc) - I was just curious, considering CM has been around for (at least) 6 years. |
||
− | :Since no-one else has asked for it, I'll just leave it to MediaWiki to decide when/if CM support is added :-) |
||
− | :— [[User:Atravers|Atravers]] 20:40 15 March 2021 (UTC) |
||
+ | <haskell> |
||
− | Hmm...I see you've added a historical-purposes-only note to 'Hawiki migration' - was moving 'Nondeterminism' an error? |
||
+ | [(length x, head x) | x <- group xs] |
||
− | — [[User:Atravers|Atravers]] 16:55 17 March 2021 (UTC) |
||
+ | </haskell> |
||
− | :It's not an error to move 'Nondeterminism'. However, putting your [[Special:Contributions/Atravers|comment]] ''on the 'Hawiki migration''' page: |
||
− | ::14:28, 9 March 2021 Atravers (-74) . . (NonDeterminism transferred to "Nondeterminism, monadically") |
||
− | :is unnecessary, since the 'Hawiki migration' page otherwise concerns ''only'' the major migration done in 2006. —[[User:HowardBGolden|HowardBGolden]] ([[User talk:HowardBGolden|talk]]) 18:16, 17 March 2021 (UTC) |
||
− | ---- |
||
− | === Please do not remove useful work === |
||
− | My dear friend Atravers, |
||
+ | or |
||
− | This page "Atribuirea" meaning "Assignment" |
||
− | is part of the Description of a Mini DSL (domain small language) we have used to teach |
||
− | computer science in Romania,for beginners. |
||
+ | <haskell> |
||
− | Because the course is inactive from this year, there is no activity on the page. |
||
+ | [(length (x:xs), x) | (x:xs) <- group xs] |
||
− | Put please do not remove the content related to a well made Haskell project, |
||
+ | </haskell> |
||
− | even if the language implemented is a sort of little C with national keywords, |
||
− | and do not ressamble to Haskell. |
||
+ | Or writing it [[Pointfree]] (Note that the type signature is essential here to avoid hitting the [[Monomorphism Restriction]]): |
||
− | It is really very unpleasant to see |
||
− | that your work in a community is removed, |
||
− | would you like to contribute in such conditions ? |
||
+ | <haskell> |
||
− | Thank you very much, |
||
+ | encode :: Eq a => [a] -> [(Int, a)] |
||
− | Lect. Dan Popa |
||
+ | encode = map (\x -> (length x, head x)) . group |
||
− | aka "Ha$kell", |
||
+ | </haskell> |
||
− | promoter of Haskell in Romania. |
||
+ | Or (ab)using the "&&&" arrow operator for tuples: |
||
− | :I simply merged "Atribuirea" with "Rodin/FAQ", which made the separate page redundant, hence the redirection - why did I do this? |
||
+ | <haskell> |
||
− | :1. https://wiki.haskell.org/Special:WhatLinksHere/Atribuirea shows no other HsWiki pages referring to Atribuirea"; |
||
+ | encode :: Eq a => [a] -> [(Int, a)] |
||
− | :2. https://wiki.haskell.org/index.php?title=Atribuirea&action=history shows the last change was made on 05:49, 11 February 2011: over 10 years ago. |
||
+ | encode xs = map (length &&& head) $ group xs |
||
+ | </haskell> |
||
+ | Or using the slightly more verbose (w.r.t. <hask>(&&&)</hask>) Applicative combinators: |
||
− | :From my side of the Internet, it just looked like an abandoned page... |
||
+ | <haskell> |
||
− | :—[[User:Atravers|Atravers]] Thu Apr 22 23:18:43 UTC 2021 |
||
+ | encode :: Eq a => [a] -> [(Int, a)] |
||
− | ---- |
||
+ | encode = map ((,) <$> length <*> head) . pack |
||
− | === Separate "page spaces" for each language on the HsWiki === |
||
+ | </haskell> |
||
− | Hello Howard; |
||
+ | Or with the help of foldr (''pack'' is the resulting function from P09): |
||
− | What would be required to have something like: |
||
− | + | <haskell> |
|
+ | encode xs = (enc . pack) xs |
||
− | * https://wiki.haskell.org/jp/ |
||
+ | where enc = foldr (\x acc -> (length x, head x) : acc) [] |
||
− | * https://wiki.haskell.org/ru/ |
||
− | + | </haskell> |
|
+ | Or using takeWhile and dropWhile: |
||
− | so that pages can be better organised by language? |
||
+ | <haskell> |
||
− | — [[User:Atravers|Atravers]] Thu Apr 22 23:54:17 UTC 2021 |
||
+ | encode [] = [] |
||
− | ---- |
||
+ | encode (x:xs) = (length $ x : takeWhile (==x) xs, x) |
||
+ | : encode (dropWhile (==x) xs) |
||
+ | </haskell> |
||
+ | |||
+ | Or without higher order functions: |
||
+ | |||
+ | <haskell> |
||
+ | encode [] = [] |
||
+ | encode (x:xs) = encode' 1 x xs where |
||
+ | encode' n x [] = [(n, x)] |
||
+ | encode' n x (y:ys) |
||
+ | | x == y = encode' (n + 1) x ys |
||
+ | | otherwise = (n, x) : encode' 1 y ys |
||
+ | </haskell> |
||
+ | |||
+ | Or we can make use of zip and group: |
||
+ | |||
+ | <haskell> |
||
+ | import List |
||
+ | encode :: Eq a => [a] -> [(Int, a)] |
||
+ | encode xs=zip (map length l) h where |
||
+ | l = (group xs) |
||
+ | h = map head l |
||
+ | </haskell> |
||
+ | |||
+ | Or if we ignore the rule that we should use the result of P09, |
||
+ | |||
+ | <haskell> |
||
+ | encode :: Eq a => [a] -> [(Int,a)] |
||
+ | encode xs = foldr f final xs Nothing |
||
+ | where |
||
+ | f x r (Just a@(i,q)) | x == q = r (Just (i+1,q)) |
||
+ | | otherwise = a : r (Just (1, x)) |
||
+ | f x r Nothing = r (Just (1, x)) |
||
+ | |||
+ | final (Just a@(i,q)) = [a] |
||
+ | final Nothing = [] |
||
+ | </haskell> |
||
+ | |||
+ | which can become a good transformer for list fusion like so: |
||
+ | |||
+ | <haskell> |
||
+ | {-# INLINE encode #-} |
||
+ | encode :: Eq a => [a] -> [(Int,a)] |
||
+ | encode xs = build (\c n -> |
||
+ | let |
||
+ | f x r (Just a@(i,q)) | x == q = r (Just (i+1,q)) |
||
+ | | otherwise = a `c` r (Just (1, x)) |
||
+ | f x r Nothing = r (Just (1, x)) |
||
+ | |||
+ | final (Just a@(i,q)) = a `c` n |
||
+ | final Nothing = n |
||
+ | |||
+ | in |
||
+ | foldr f final xs Nothing) |
||
+ | </haskell> |
||
+ | |||
+ | Just one more way with recursion: |
||
+ | |||
+ | <haskell> |
||
+ | encode :: [[t]] -> [(Int, t)] |
||
+ | encode = let f acc [] = acc |
||
+ | f acc (x:xs) = f ((length x, head x): acc) xs |
||
+ | in reverse . f [] |
||
+ | </haskell> |
||
+ | |||
+ | |||
+ | [[Category:Programming exercise spoilers]] |
Latest revision as of 03:45, 19 May 2021
(*) Run-length encoding of a list.
Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.
encode xs = map (\x -> (length x,head x)) (group xs)
which can also be expressed as a list comprehension:
[(length x, head x) | x <- group xs]
or
[(length (x:xs), x) | (x:xs) <- group xs]
Or writing it Pointfree (Note that the type signature is essential here to avoid hitting the Monomorphism Restriction):
encode :: Eq a => [a] -> [(Int, a)]
encode = map (\x -> (length x, head x)) . group
Or (ab)using the "&&&" arrow operator for tuples:
encode :: Eq a => [a] -> [(Int, a)]
encode xs = map (length &&& head) $ group xs
Or using the slightly more verbose (w.r.t. (&&&)
) Applicative combinators:
encode :: Eq a => [a] -> [(Int, a)]
encode = map ((,) <$> length <*> head) . pack
Or with the help of foldr (pack is the resulting function from P09):
encode xs = (enc . pack) xs
where enc = foldr (\x acc -> (length x, head x) : acc) []
Or using takeWhile and dropWhile:
encode [] = []
encode (x:xs) = (length $ x : takeWhile (==x) xs, x)
: encode (dropWhile (==x) xs)
Or without higher order functions:
encode [] = []
encode (x:xs) = encode' 1 x xs where
encode' n x [] = [(n, x)]
encode' n x (y:ys)
| x == y = encode' (n + 1) x ys
| otherwise = (n, x) : encode' 1 y ys
Or we can make use of zip and group:
import List
encode :: Eq a => [a] -> [(Int, a)]
encode xs=zip (map length l) h where
l = (group xs)
h = map head l
Or if we ignore the rule that we should use the result of P09,
encode :: Eq a => [a] -> [(Int,a)]
encode xs = foldr f final xs Nothing
where
f x r (Just a@(i,q)) | x == q = r (Just (i+1,q))
| otherwise = a : r (Just (1, x))
f x r Nothing = r (Just (1, x))
final (Just a@(i,q)) = [a]
final Nothing = []
which can become a good transformer for list fusion like so:
{-# INLINE encode #-}
encode :: Eq a => [a] -> [(Int,a)]
encode xs = build (\c n ->
let
f x r (Just a@(i,q)) | x == q = r (Just (i+1,q))
| otherwise = a `c` r (Just (1, x))
f x r Nothing = r (Just (1, x))
final (Just a@(i,q)) = a `c` n
final Nothing = n
in
foldr f final xs Nothing)
Just one more way with recursion:
encode :: [[t]] -> [(Int, t)]
encode = let f acc [] = acc
f acc (x:xs) = f ((length x, head x): acc) xs
in reverse . f []