3

我目前正在学习函数式编程和来自 python 背景的 Haskell。为了帮助我学习，我决定做一些项目欧拉问题（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]]
  1. 有没有办法在没有 lambda 的情况下编写该转换函数并使其更具可读性？

  2. 如何将此嵌套数组转换为定义如下的树结构：

    数据树 a = EmptyTree | 节点 a (Tree a) (Tree a) 推导 (Show, Read, Eq)

    或者将它保留为数组并从那里解决它会更容易吗？

4

3 回答 3

4

这是我想出的

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
于 2013-08-31T18:52:58.630 回答
2

Tree您可以使用以下方法将列表列表转换为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

请注意同一棵树如何被重用为上一代中两棵不同树的子代。

向后考虑可能会有所帮助

  • 最后一行中的每个元素都有一个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]]

你是对的，你不需要生成这个中间数据结构来解决这个问题，但是你可以使用这个相同的结构来直接计算你的答案。

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
于 2013-09-01T00:21:25.263 回答
1

我喜欢嵌套列表，可能是因为我对树不太了解……这里有一个提示：

如果你从最长的n数字行（即n选项）开始，你能把它转换成一个n-1数字/选项的行，每一个对应于前一行的一个数字/选项吗？

（以嵌套列表为参数，可以用 Haskell 一行代码解决）

于 2013-08-31T21:05:33.663 回答