Pomoc w programowaniu, odpowiedzi na pytania / Haskell / Projekt Euler # 18 w Haskell - haskell, drzewo

Projekt Euler # 18 w Haskell - haskell, drzewo

Obecnie uczę się programowania funkcjonalnego i Haskella pochodzącego z tła python. Aby pomóc mi się uczyć, postanowiłem zrobić kilka problemów związanych z projektem (http://projecteuler.net/problem=18). Obecnie jestem na # 18. Zaczynając od tego ciągu,

"75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"

Udało mi się przekonwertować go do zagnieżdżonej tablicy za pomocą tej funkcji:

map (x -> map (y -> read y :: Int) (words x)) (lines a)

Ta funkcja wyprowadza to:

[[75],[95,64],[17,47,82],[18,35,87,10],[20,4,82,47,65],[19,1,23,75,3,34],[88,2,77,73,7,63,67],[99,65,4,28,6,16,70,92],[41,41,26,56,83,40,80,70,33],[41,48,72,33,47,32,37,16,94,29],[53,71,44,65,25,43,91,52,97,51,14],[70,11,33,28,77,73,17,78,39,68,17,57],[91,71,52,38,17,14,91,43,58,50,27,29,48],[63,66,4,68,89,53,67,30,73,16,69,87,40,31],[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]

Czy istnieje sposób, aby napisać tę funkcję konwersji bez lambdas i make jest bardziej czytelny?
Jak mogę przekonwertować tę zagnieżdżoną tablicę na drzewo struktura zdefiniowana jak poniżej:

drzewo danych a = EmptyTree | Węzeł a (Drzewo a) (Drzewo a) czerpiące (Pokaż, Odczyt, Eq)

A może po prostu łatwiej byłoby zostawić to jako tablicę i rozwiązać od tego?

Odpowiedzi:

2 dla odpowiedzi № 1

Możesz przekonwertować listę list na Tree używając foldr:

-- given the elements for the current generation of trees,
-- and a list of trees in the next generation, generate
-- the current generation of trees
-- assumes |as| == |ts| - 1
generation :: [a] -> [Tree a] -> [Tree a]
generation as ts = zipWith3 Node as (init ts) (tail ts)

-- forest gs ~ generates |head gs| trees
forest :: [[a]] -> [Tree a]
forest = foldr generation $ repeat EmptyTree

fromList :: [[a]] -> Maybe (Tree a)
fromList gs = case forest gs of
[t] -> Just t
_   -> Nothing

Zauważ, jak to samo drzewo jest używane jako dziecko dwóch różnych drzew w poprzednim pokoleniu.

Może pomóc w przemyśleniu go wstecz

każdy element w ostatnim wierszu dostaje EmptyTree jako lewe i prawe dziecko.

generation as ts = zipWith3 Node as (init ts) (tail ts)
as = [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]
ts = [EmptyTree, EmptyTree, ..]
init ts = [EmptyTree, EmptyTree, ..]
tail ts = [EmptyTree, EmptyTree, ..]
zipWith3 Node as (init ts) (tail ts) = [Node 4 EmptyTree EmptyTree,Node 62 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 27 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree,Node 9 EmptyTree EmptyTree,Node 70 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 73 EmptyTree EmptyTree,Node 93 EmptyTree EmptyTree,Node 38 EmptyTree EmptyTree,Node 53 EmptyTree EmptyTree,Node 60 EmptyTree EmptyTree,Node 4 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree]

każdy element w następnym wierszu używa drzew z ostatniego wiersza

generation as ts = zipWith3 Node as (init ts) (tail ts)
as = [63,66,4,68,89,53,67,30,73,16,69,87,40,31]
ts = [Node 4 EmptyTree EmptyTree,Node 62 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 27 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree,Node 9 EmptyTree EmptyTree,Node 70 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 73 EmptyTree EmptyTree,Node 93 EmptyTree EmptyTree,Node 38 EmptyTree EmptyTree,Node 53 EmptyTree EmptyTree,Node 60 EmptyTree EmptyTree,Node 4 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree]
init ts = [Node 4 EmptyTree EmptyTree,Node 62 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 27 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree,Node 9 EmptyTree EmptyTree,Node 70 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 73 EmptyTree EmptyTree,Node 93 EmptyTree EmptyTree,Node 38 EmptyTree EmptyTree,Node 53 EmptyTree EmptyTree,Node 60 EmptyTree EmptyTree,Node 4 EmptyTree EmptyTree]
tail ts = [Node 62 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 27 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree,Node 9 EmptyTree EmptyTree,Node 70 EmptyTree EmptyTree,Node 98 EmptyTree EmptyTree,Node 73 EmptyTree EmptyTree,Node 93 EmptyTree EmptyTree,Node 38 EmptyTree EmptyTree,Node 53 EmptyTree EmptyTree,Node 60 EmptyTree EmptyTree,Node 4 EmptyTree EmptyTree,Node 23 EmptyTree EmptyTree]
zipWith3 Node as (init ts) (tail ts) = [Node 63 (Node 4 EmptyTree EmptyTree) (Node 62 EmptyTree EmptyTree),Node 66 (Node 62 EmptyTree EmptyTree) (Node 98 EmptyTree EmptyTree),Node 4 (Node 98 EmptyTree EmptyTree) (Node 27 EmptyTree EmptyTree),Node 68 (Node 27 EmptyTree EmptyTree) (Node 23 EmptyTree EmptyTree),Node 89 (Node 23 EmptyTree EmptyTree) (Node 9 EmptyTree EmptyTree),Node 53 (Node 9 EmptyTree EmptyTree) (Node 70 EmptyTree EmptyTree),Node 67 (Node 70 EmptyTree EmptyTree) (Node 98 EmptyTree EmptyTree),Node 30 (Node 98 EmptyTree EmptyTree) (Node 73 EmptyTree EmptyTree),Node 73 (Node 73 EmptyTree EmptyTree) (Node 93 EmptyTree EmptyTree),Node 16 (Node 93 EmptyTree EmptyTree) (Node 38 EmptyTree EmptyTree),Node 69 (Node 38 EmptyTree EmptyTree) (Node 53 EmptyTree EmptyTree),Node 87 (Node 53 EmptyTree EmptyTree) (Node 60 EmptyTree EmptyTree),Node 40 (Node 60 EmptyTree EmptyTree) (Node 4 EmptyTree EmptyTree),Node 31 (Node 4 EmptyTree EmptyTree) (Node 23 EmptyTree EmptyTree)]

zipWith3 f as bs cs po prostu pobiera elementy z każdej listy w kroku i stosuje daną funkcję do elementów o tym samym indeksie, podając [ f a0 b0 c0, f a1 b1 c1, ... ]

Możesz także obliczyć to bezpośrednio za pomocą forest [[63,66,4,68,89,53,67,30,73,16,69,87,40,31],[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]

Masz rację, że nie jesteś potrzeba generowanie tej pośredniej struktury danych w celu rozwiązania problemu, ale możesz użyć tej samej struktury do obliczenia swojej odpowiedzi bezpośrednio.

generation :: Num a => [a] -> [(a, [a])] -> [(a, [a])]
generation as ts = zipWith3 ????  as (init ts) (tail ts)

forest :: Num a => [[a]] -> [(a, [a])]
forest = foldr generation $ repeat ????

fromList :: [[a]] -> Maybe (a, [a])
fromList gs = case forest gs of
[t] -> Just t
_   -> Nothing

-- what"s the maximum total sum of any path
maxTotal :: [[a]] -> Maybe a
maxTotal = fmap fst . fromList

-- what"s the path with maximum total sum
maxPath :: [[a]] -> Maybe [a]
maxPath = fmap snd . fromList

4 dla odpowiedzi nr 2

Oto, co wymyśliłem

foo :: String -> [[Int]]
foo = map (map read) . map words . lines

Drzewo może być zbudowane z tego przy użyciu definicji rekursywnej.

fromList :: [[a]] -> Tree a
fromList [[]] = EmptyTree
fromList [[x]] = Node x EmptyTree EmptyTree
fromList ([x]:rs) = Node x ltree rtree
where ltree = fromList . snd $ mapAccumL (n l -> (n+1,take n l)) 1 rs
rtree = fromList $ map (drop 1) rs

1 dla odpowiedzi nr 3

Lubię listę zagnieżdżoną, może dlatego, że nie wiem zbyt wiele o drzewach ... tutaj jest wskazówka:

Jeśli zaczniesz od najdłuższej linii z n liczby (czyli n do wyboru), czy możesz przekonwertować go na linię z n-1 liczby / wybory, z których każdy odpowiada numerowi / wyborowi na linii przed?

(z zagnieżdżoną listą jako parametrem, możesz zakodować rozwiązanie w jednym wierszu z Haskellem)