Отрезание Ленивого Списка

Question

Мне было интересно, есть ли у кого-нибудь понимание того, как создать функцию, которая будет принимать список и возвращать только те термины, которые могут быть сгенерированы за x раз.

Например, у меня есть функцияэто займет около 10 минут, чтобы вернуть только несколько терминов.Вместо того, чтобы угадывать, сколько терминов я смогу сгенерировать (с помощью дубля x), я хотел бы просто добавить бесконечный список в мою неэффективную функцию и иметь отдельную функцию, решающую, когда истечь время.

Так что-то вроде этого: [5,7,10] = takeUntilTime (10 sec) . inefficientFunction $ [1..]

Я довольно новичок в Haskell, но я думаю, что могу написать эту функцию, чтобы просто проверять таймер после того, как каждый новый термин генерируется и останавливается, если время истекло.

Однако, что если 4-й срок займет вечность?Был бы способ остановить неэффективную функцию от завершения генерации этого 4-го члена, даже если он уже начался?

У меня нет больших надежд на прямой ответ, но я ценю любую интуицию по этому поводу.Спасибо.

Answer 1

Не проходили много испытаний, но, похоже, это работает, по крайней мере, в небольших масштабах.

import Control.Concurrent
import Control.Exception
import Control.Monad

takeUntilTime :: Int -> [a] -> IO [a]
takeUntilTime limit list = do
    me <- myThreadId
    bracket (forkIO $ threadDelay limit >> throwTo me NonTermination) killThread
        . const $ tryTake list
  where
    (/:/) = liftM2 (:)
    tryTake list = handle (\NonTermination -> return []) $
        case list of
            [] -> return []
            x:xs -> evaluate x /:/ tryTake xs

ghci> takeUntilTime 1000000 [x | x <- [1..], x == 0]
[]
(1.02 secs, 153111264 bytes)
ghci> takeUntilTime 1000000 [maximum [y `mod` x | y <- [1..100000]] | x <- [1..]]
[0,1,2,3]
(1.00 secs, 186234264 bytes)

Answer 2

Я думаю, что вы хотите это: System.Timeout

Это позволяет тайм-аутам событий ввода-вывода.У него есть функция, тип которой:

timeout :: Int -> IO a -> IO (Maybe a)

Я думаю, вы должны использовать это.Я бы сделал это, используя функцию тайм-аута и подход «Итеративное углубление», чтобы все больше и больше влить в вашу функцию, пока она не заработает.Таким образом, когда кто-то, наконец, достигает тайм-аута, вы знаете, что зашли достаточно далеко.

Answer 3

Вдохновленный ответом ephemient Я решил опубликовать два обобщения его решения.

Раствор 1

import Control.Concurrent
import Control.Exception
import Control.Monad

doUntilTime :: Int -> IO a {- must handle NonTermination exception! -} -> IO a
doUntilTime limit action = do
  me <- myThreadId
  bracket (forkIO $ threadDelay limit >> throwTo me NonTermination) killThread
           . const $ action

Пример

(/:/) = liftM2 (:)
tryTake list = handle (\NonTermination -> return []) $
   case list of
     [] -> return []
     x:xs -> evaluate x /:/ tryTake xs

test = do
  res <- doUntilTime 1000000 (tryTake [1..])
  putStrLn (show $ length res)

Решение 2

В этом решении вы передаете значение по умолчанию , вход и предрекурсивную функцию doUntilTime.

Предрекурсивная функция написана в стиле, где первый параметр, давайте назовем его self, используется там, где вы использовали бы рекурсивный вызов раньше. Это избавит вас от необходимости обрабатывать исключение NonTermination явно.

import Control.Concurrent
import Control.Exception
import Control.Monad

doUntilTime :: Int -> a -> b -> ((a -> IO b) -> (a -> IO b)) -> IO b
doUntilTime limit input defaultVal action = do
    me <- myThreadId
    bracket (forkIO $ threadDelay limit >> throwTo me NonTermination) killThread
        . const $ fix action input
  where
    fix f = f (\a -> handle (\NonTermination -> return defaultVal) (fix f a))

(/:/) = liftM2 (:)

-- tryTake is written in a "pre-recursive" style. There are no
-- occurrences of "tryTake" in the body only occurrences of
-- "self" (the first parameter)
tryTake :: ([Int] -> IO [Float]) -> ([Int] -> IO [Float])
tryTake self list =
   case list of
     [] -> return []
     x:xs -> evaluate (fromIntegral x) /:/ self xs

test = do
  res <- doUntilTime 1000000 [1..] [] tryTake
  print (length res)

Answer 4

Я думаю, вы задали два вопроса. 1. Как установить ограничение по времени для извлечения элементов из бесконечного списка. 2. Как подключить блокирующую функцию или создать неблокирующую функцию, как некоторые сетевые функции ввода-вывода.

Для второго, вы можете обратиться к http://twelvestone.com/forum_thread/view/32028 для некоторой идеи. Тогда для первого можно предположить, что неэффективная функция неблокирующая.