Jak mieć wiele nieskończonych zakresów w zrozumieniu listy?

Question

w Haskell Mam listę zrozumieniem tak:

sq = [(x,y,z) | x <- v, y <- v, z <- v, x*x + y*y == z*z, x < y, y < z] 
    where v = [1..] 

Jednak gdy próbuję take 10 sq, to po prostu zawiesza ... Czy istnieje sposób, aby obsłużyć wiele zakresów nieskończone?

Dzięki

Answer 1

Jest to możliwe, ale będziesz musiał wymyślić kolejności, w jakiej do generowania liczb. Poniższe generuje liczby, które chcesz; pamiętać, że test x < y może być zastąpiony przez generowanie tylko y które są >x i podobnie dla z (która jest określana raz x i y są zobowiązane):

[(x, y, z) | total <- [1..] 
      , x <- [1..total-2] 
      , y <- [x..total-1] 
      , z <- [total - x - y] 
      , x*x + y*y == z*z] 

Answer 2

kodzie zamrożenie bo twoje orzekać nigdy nie zostały spełnione.
Dlaczego?

Weźmy przykład bez żadnego orzecznika, aby to zrozumieć.

>>> let v = [1..] in take 10 $ [ (x, y, z) | x <- v, y <- v, z <- v ] 
[(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,1,5),(1,1,6),(1,1,7),(1,1,8),(1,1,9),(1,1,10)] 

Jak widać x i y zawsze będą oceniane na 1, ponieważ z nigdy nie przestanie rosnąć.
Wtedy twój predykat nie może być.

Jakiekolwiek obejście?

Spróbuj zrozumieć pojęcie "Lista zagnieżdżona".

>>> [[ fun x y | x <- rangeX, predXY] | y <- rangeY, predY ] 

lub równolegle listowego, które mogą być aktywowane za pomocą,

>>> :set -XParallelListComp 

odnośnika na doc

Answer 3

listowe listy przeliczane są zagnieżdżone zastosowań funkcji concatMap:

concatMap :: (a -> [b]) -> [a] -> [b] 
concatMap f xs = concat (map f xs) 

concat :: [[a]] -> [a] 
concat [] = [] 
concat (xs:xss) = xs ++ concat xss 

-- Shorter definition: 
-- 
-- > concat = foldr (++) [] 

Twój przykład jest równoważny t do tego:

sq = concatMap (\x -> concatMap (\y -> concatMap (\z -> test x y z) v) v) v 
    where v = [1..] 
      test x y z = 
       if x*x + y*y == z*z 
       then if x < y 
        then if y < z 
         then [(x, y, z)] 
         else [] 
        else [] 
       else [] 

Jest to w zasadzie podejście "zagnieżdżone pętle"; najpierw spróbuje x = 1, y = 1, z = 1, a następnie przejdzie do x = 1, y = 1, z = 2 itd., dopóki nie spróbuje wszystkich elementów listy jako wartości dla z; tylko wtedy może przejść do wypróbowania kombinacji z y = 2.

Ale oczywiście możesz zobaczyć problem - ponieważ lista jest nieskończona, nigdy nie zabraknie wartości, które można wypróbować pod kątem z. Tak więc kombinacja (3, 4, 5) może występować tylko po nieskończenie wielu innych kombinacjach, dlatego Twój kod jest zawsze w pętli.

Aby rozwiązać ten problem, musimy generować trójki w bardziej inteligentny sposób, tak aby w przypadku dowolnej kombinacji generator osiągnął go po skończonej liczbie kroków.Studiować ten kod (który obsługuje tylko pary, a nie trzykrotnie):

-- | Take the Cartesian product of two lists, but in an order that guarantees 
-- that all combinations will be tried even if one or both of the lists is 
-- infinite: 
cartesian :: [a] -> [b] -> [(a, b)] 
cartesian [] _ = [] 
cartesian _ [] = [] 
cartesian (x:xs) (y:ys) = 
    [(x, y)] ++ interleave3 vertical horizontal diagonal 
     where 
      -- The trick is to split the problem into these four pieces: 
      -- 
      -- |(x0,y0)| (x0,y1) ... horiz 
      -- +-------+------------ 
      -- |(x1,y0)| . 
      -- | . | . 
      -- | . | . 
      -- | . | . 
      -- vert   diag 
      vertical = map (\x -> (x,y)) xs 
      horizontal = map (\y -> (x,y)) ys 
      diagonal = cartesian xs ys 


interleave3 :: [a] -> [a] -> [a] -> [a] 
interleave3 xs ys zs = interleave xs (interleave ys zs) 

interleave :: [a] -> [a] -> [a] 
interleave xs [] = xs 
interleave [] ys = ys 
interleave (x:xs) (y:ys) = x : y : interleave xs ys 

Aby zrozumieć ten kod (i naprawić, jeśli zawiedli!) Spojrzeć na this blog entry on how to count infinite sets, a na czwartym wykresie w szczególności-funkcja jest algorytm oparty na tym "zygzaku"!

Właśnie wypróbowałem prostą wersję twojego sq używając tego; prawie natychmiast znajduje (3,4,5), ale potem zajmuje bardzo dużo czasu, aby dostać się do dowolnej innej kombinacji (przynajmniej w GHCI). Ale myślę, że kluczowymi lekcjami, które można od tego odjąć, są:

1. Zrozumienie list nie działa dobrze w przypadku zagnieżdżonych nieskończonych list.
2. Nie spędzaj zbyt wiele czasu na zabawie ze zrozumieniem listy. Wszystko, co mogą zrobić, działa tak jak map, filter i concatMap może - w dodatku istnieje wiele innych użytecznych funkcji w the list library, więc skoncentruj swoje wysiłki na tym.

Answer 4

W uzupełnieniu do innych odpowiedzi wyjaśniając problem, tu jest alternatywne rozwiązanie, uogólnione pracować level-monad i stream-monad że nadają się do badań nad przestrzeni nieskończonego wyszukiwania (Jest również kompatybilny z listy monady i logict, ale te nie będą grać ładnie z nieskończonych przestrzeni poszukiwań, jak już dowiedziałem):

{-# LANGUAGE MonadComprehensions #-} 

module Triples where 

import Control.Monad 

sq :: MonadPlus m => m (Int, Int, Int) 
sq = [(x, y, z) | x <- v, y <- v, z <- v, x*x + y*y == z*z, x < y, y < z] 
    where v = return 0 `mplus` v >>= (return . (1+)) 

teraz na szybkie przeszukiwanie wszerz:

*Triples> :m +Control.Monad.Stream 
*Triples Control.Monad.Stream> take 10 $ runStream sq 
[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17),(12,16,20),(7,24,25), 
(15,20,25),(10,24,26),(20,21,29)] 

alternatywnie:

*Triples> :m +Control.Monad.Levels 
*Triples Control.Monad.Levels> take 5 $ bfs sq -- larger memory requirements 
[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17)] 
*Triples Control.Monad.Levels> take 5 $ idfs sq -- constant space, slower, lazy 
[(3,4,5),(5,12,13),(6,8,10),(7,24,25),(8,15,17)]