Циклы в Haskell???
Сегодня, дорогие друзья, мы будем отвечать на страшный и неизмеримый в своей жестокости вопрос: «как на Haskell написать цикл for??!?»
Многие полегли, пытаясь объяснить очередному процедурщику, как же так случилось, что в мире ФП нету циклов. Пора процедурщикам сделать ответ на эти заявления. Сегодня мы делаем полный бред и несусветную чушь, а именно - циклы на Haskell.
Разумеется, всё представленное - не более чем симуляция циклов. Однако в данном случае нас будет волновать форма, а не содержание.
Итак, приступим. Первый вопрос - куда в функциональную программу запихать циклы? Правильно. Никуда. Поэтому циклы мы будем запихивать в монады. Для наибольшего охвата нашего коварного замысла свежеобретённая сущность должна быть трансформером монад.
Зададимся вопросом - что по сути (чисто внешне) представляет собой обыденный процедурный цикл?
- Повторяющиеся действия из тела цикла;
- Оператор break;
- Оператор continue;
Если воссоздание первого пункта - довольно очевидная задача, то со вторым и третьим всё сложнее. Мы не будем долго думать и введём две переменные «был брейк» и «был континью», одна из которых должна выходить из тела цикла выбрасывать нас из процесса повторения, а вторая - выходить из тела цикла, но повторение не завершать.
За основу возьмём известный (всем кто знаком с mtl) трансформер StateT, но поведение его как монады придётся немного переписать.
newtype LoopT m a = LoopT { runLoopT :: (Bool,Bool) -> m (Maybe a,Bool,Bool) } Содержание вместо типа а в выводе типа Maybe a объясняется просто - когда нам потребуется выброситься из тела цикла, текущий результат нужно будет чем нибудь заменить. Поскольку это "что нибудь" должно иметь соответствующий тип, который нам взять негде, мы используем тип, экземпляр которого у нас есть всегда.
instance (Monad m) => Monad (LoopT m) where return a = LoopT $ \(l,i) -> return (Just a, l, i) m >>= k = LoopT $ \(l,i) -> do ~(a, l'', i'') <- runLoopT m (l,i) case (a, l'', i'') of (Just a'',True,True) -> runLoopT (k a'') (l'',i'') _ -> return (Nothing,l'',i'') fail str = LoopT $ \_ -> fail str instance MonadTrans (LoopT) where lift m = LoopT $ \(l,i) -> do a <- m return (Just a, l, i)
Можно заметить, что один из имеющихся Bool (а именно, тот, что отвечает за continue), в принципе, дублирует свои функции с использованным в монаде Maybe a, но, для наглядности было решено оставить и то, и другое.
Наши continue и break:
lbreak :: (Monad m) => LoopT m () lbreak = LoopT $ \(_,i) -> return (Just (),False,i) lcontinue :: (Monad m) => LoopT m () lcontinue = LoopT $ \(_,_) -> return (Just (),True, False) Для начала, попробуем сделать бесконечный цикл. В самом деле, наличие оператора break даёт нам возможность его закончить. Цикл, разумеется, симулируется посредством рекурсии, но это тссс...
foreverl :: (Monad m) => LoopT m () -> m () foreverl m = do ~(_, l, i) <- runLoopT m (True,True) when (l) $ foreverl m return () Похожие принципы можно использовать и для производства других циклов. Как настоящим процедурщикам, нам жизненно необходимы циклы while, do-while, for и foreach.
while :: (Monad m) => m Bool -> LoopT m () -> m () while pred m = do pred' <- pred when (pred') $ do ~(_, l, i) <- runLoopT m (True,True) when (l) $ while pred m return () dowhile :: (Monad m) => m Bool -> LoopT m () -> m () dowhile pred m = do ~(_, l, i) <- runLoopT m (True,True) pred' <- pred when (l && not pred') $ dowhile pred m return () for :: (Monad m) => Int -> Int -> (Int -> LoopT m ()) -> m () for start end body | (start < end) = do ~(_, l, i) <- runLoopT (body start) (True,True) when (l) $ for (start+1) end body | otherwise = return () foreach :: (Monad m) => [a] -> (a -> LoopT m ()) -> m () foreach [] _ = return () foreach (h:t) body = do ~(_, l, i) <- runLoopT (body h) (True,True) when (l) $ foreach t body Забавно, что наш процедурный foreach прекрасно работает с бесконечными списками (break же есть). Ну и маленький примерчик использования
type TestState = State [Int] tst :: TestState () tst = do s <- get foreach s $ \ v -> do when(v < 3) lcontinue lift $ modify (\l -> v:l) when(v == 10) lbreak return ()
> take 20 $ execState tst [1..]
[10,9,8,7,6,5,4,3,1,2,3,4,5,6,7,8,9,10,11,12]
Интересной особенностью подобных трансформеров является то, что для использования полный тип знать вообще не нужно.
Я просто оставлю это здесь, хорошо?)