۲۲ - ۷استخدام برای برنامه‌نویسی با یه کلکِ عجیب

بعضی شرکت‌ها برای فیلتر‌کردن (نه برای تست‌کردن) متقاضی‌های شغل‌های نرم‌افزاری، از FizzBuzz استفاده می‌کنن. صورت مسئله اینه:

برنامه‌ای بنویسین که اعداد ۱ تا ۱۰۰ رو چاپ می‌کنه. اما بجای مضارب ۳ چاپ کنه ‏‎“Fizz”‎‏ و بجای مضارب ۵ چاپ کنه ‏‎“Buzz”‎‏. برای اعدادی که هم مضرب ۳ هستن و هم مضرب ۵، چاپ کنه ‏‎“FizzBuzz”‎‏.

یه راه حل معمولی با هسکل می‌تونه این شکلی باشه:

fizzBuzz :: Integer -> String
fizzBuzz n | n `mod` 15 == 0 = "FizzBuzz"
           | n `mod` 5  == 0 = "Buzz"
           | n `mod` 3  == 0 = "Fizz"
           | otherwise       = show n

main :: IO ()
main =
  mapM_ (putStrLn . fizzBuzz) [1..100]

با استِیت ‏‎FizzBuzz‎‏ نوشتن تنبیه خوبیه! ببینیم با ‏‎State‎‏ چطور میشه:

import Control.Monad
import Control.Monad.Trans.State

fizzBuzz :: Integer -> String
fizzBuzz n | n `mod` 15 == 0 = "FizzBuzz"
           | n `mod` 5  == 0 = "Buzz"
           | n `mod` 3  == 0 = "Fizz"
           | otherwise       = show n

fizzbuzzList :: [Integer] -> String
fizzbuzzList list =
  execState (mapM_ addResult list) []

addResult :: Integer -> State [String] ()
addResult n = do
    xs <- get
    let result = fizzBuzz n
    put (result : xs)

دقت کنین که ‏‎State‎‏ در واقع یه تایپ مستعار برای ‏‎StateT‎‏ که وارد کردین‌ه:

main :: IO ()
main =
  mapM_ putStrLn $
    reverse $ fizzbuzzList [1..100]

قسمت خوبش اینه که قبل از دادن جواب‌ها به خروجی استاندارد (به واسطه‌ی ‏‎putStrLn‎‏)، اول داده‌ها رو جمع‌آوری می‌کنیم. بدی‌ش اینه که یه لیست رو معکوس می‌کنیم. معکوس کردنِ لیست‌های تک-پیوندی خیلی خوب نیست، حتی تو هسکل؛ با لیستِ بینهایت هم به جواب نمیرسه. یه موردِ دیگه، ورودی‌ای می‌گیریم که اعدادِ مورد استفاده برای FizzBuzz رو به صورت خطی از اول تا انتها تعیین می‌کنه.

دو راه برای مدیریت ِ این وجود داره. یکی استفاده از ‌نوع‌داده‌ایه که اضافه کردنِ المان به انتهاش کم هزینه‌تر باشه. استفاده از ‏‎(++)‎‏ به صورتِ بازگشتی ممکنه خیلی سنگین بشه، پس از یه چیزی استفاده کنیم که با زمانِ ثابت به انتها المان اضافه کنه. لیستِ دیفرنس با O(1) المان‌ها رو به انتها اضافه می‌کنه.

import Control.Monad
import Control.Monad.Trans.State
-- http://hackage.haskell.org/package/dlist
import qualified Data.DList as DL

fizzBuzz :: Integer -> String
fizzBuzz n | n `mod` 15 == 0 = "FizzBuzz"
           | n `mod` 5  == 0 = "Buzz"
           | n `mod` 3  == 0 = "Fizz"
           | otherwise       = show n

fizzbuzzList :: [Integer] -> [String]
fizzbuzzList list =
  let dlist =
        execState (mapM_ addResult list)
                  DL.empty
     -- برگشتن به لیست معمولی
  in DL.apply dlist []

addResult :: Integer
          -> State (DL.DList String) ()
addResult n = do
    xs <- get
    let result = fizzBuzz n
    -- ‎‏که به اول اضافه می‌کنه،‏‎ cons برخلاف
    -- ‎‏می‌کنه.‏‎ append به انتها snoc
    put (DL.snoc xs result)

main :: IO ()
main =
  mapM_ putStrLn $ fizzbuzzList [1..100]

اگه GHC ۷٫۱۰ یا جدیدتر دارین، ‏‎mapM_‎‏ با هر ‏‎Foldable‎‏ ای کار می‌کنه (نه فقط لیست). اونطوری میشه یه کم تمیزتر نوشت:

Prelude> :t mapM_
mapM_ :: (Monad m, Foldable t)
      => (a -> m b) -> t a -> m ()

اگه تبدیلِ به لیست رو بسپاریم به نمونه ِ ‏‎Foldable‎‏ ِ تایپِ ‏‎DList‎‏، می‌تونیم مقداری کُد رو حذف کنیم:

fizzbuzzList :: [Integer]
             -> DL.DList String
fizzbuzzList list =
  execState (mapM_ addResult list) DL.empty

addResult :: Integer
          -> State (DL.DList String) ()
addResult n = do
    xs <- get
    let result = fizzBuzz n 
    put (DL.snoc xs result)

main :: IO ()
main =
  mapM_ putStrLn $ fizzbuzzList [1..100]

نمونه ِ ‏‎Foldable‎‏ ِ تایپِ ‏‎DList‎‏ به خاطر محدودیت‌هایی که این نوع‌داده داره، قبل از فولد‌کردن تبدیل به لیست میشه. افزودن به انتها ِ ارزون داریم، ولی نمیشه قبل از درست‌کردنِ کلِ ساختار "ببینیم" چی درست شده. این مبحث رو با جزئیات بیشتر تو فصلِ بعد توضیح میدیم.

شاید به نظرتون اومده باشه که اینجا استفاده از ‏‎State‎‏ یه کم اضافی بود. حق دارین! برای چنین کاربردهایی تو هسکل، ‏‎State‎‏ رایج نیست. شاید برای بهینه‌سازیِ انتخابی از یه نوعِ دیگه ‏‎State‎‏ به اسمِ ‏‎ST‎‏ استفاده کنین، ولی ‏‎State‎‏ به‌خودیِ‌خود یه کم سلیقه‌ایه. در استفاده، یا استفاده نکردن از ‏‎State‎‏ احساسِ هیچ فشاری نکنین. لطفاً چندتا مصاحبه‌گرِ استخدام رو با اون FizzBuzz ِ عجیب بترسونین. از اونی که نشون دادیم هم پیچیده‌تر بنویسین!

FizzBuzz متفاوت

یه تمرینه! بجای اینکه ساختار داده رو تغییر بدین، اون مشکلِ معکوس کردنِ لیست رو اینطوری درست کنین:

fizzbuzzFromTo :: Integer
               -> Integer
               -> [String]
fizzbuzzFromTo = undefined

باز هم توی لیستِ خروجی cons کنین، اما شمارش رو برعکس شروع کنین تا ترتیب‌شون درست دربیاد. این روش برای حذفِ ‏‎reverse‎‏ های اضافی رایج‌تره.