在Haskell项目欧拉＃18
我目前正在学习函数式编程，Haskell来自python背景。 为了帮助我学习，我决定做一些项目问题（http://projecteuler.net/problem=18）。 目前我在＃18。 从这个字符串开始，
"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"
我设法使用这个函数将它转换成一个嵌套数组：
map (x -> map (y -> read y :: Int) (words x)) (lines a)
该功能输出：
[[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]]
我将如何将这个嵌套数组转换为像这样定义的树结构：
数据树a = EmptyTree | 节点a（Tree a）（Tree a）派生（Show，Read，Eq）
或者将它作为一个数组并从那里解决它会更容易？
您可以使用foldr将列表的列表转换为Tree ：
-- 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
请注意，同一棵树如何被重用为上一代中两棵不同树的孩子。
这可能有助于反思
最后一行中的每个元素都将EmptyTree作为左侧和右侧子级。
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]
倒数第二行中的每个元素都使用最后一行中的树
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只是在步骤中从每个列表中获取元素，并将给定的函数应用于具有相同索引的元素，给出[ f a0 b0 c0, f a1 b1 c1, ... ]
你也可以通过使用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]]直接计算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]]
你是对的，你不需要为了解决这个问题而生成这个中间数据结构，但是你可以使用相同的结构来直接计算你的答案。
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
这是我想出来的
foo :: String -> [[Int]]
foo = map (map read) . map words . lines
树可以使用递归定义从此构造。
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
我喜欢嵌套列表，也许是因为我对树木不太了解......这里有个提示：
如果你从最长的行开始，有n数字（也就是n选择），你可以把它转换成一行有n-1数字/选择的行，每行对应一行中的数字/选择？
（使用嵌套列表作为参数，您可以使用Haskell将解决方案编码在一行中）
链接地址: http://www.djcxy.com/p/80425.html