Haskell-Project Euler 4-Java 学习之路

我是Haskell的新手，我认为要想开始编写haskell程序，我可以解决一些项目的euler问题 .

所以我继续使用它并实现了Project Euler的第4个问题 .

问题陈述：

回文数字两种方式相同 . 由两个2位数字的乘积制成的最大回文是9009 = 91×99 .

找到由两个3位数字的乘积制成的最大回文 .

但是我的解决方案似乎有问题 .

这里是：

projectEuler4 :: (Ord a,Num a) => a 

projectEuler4 = max palindromeList
  where palindromeList = [reverse(x*y)|x<-[1..999],y <- [1..999]]

GHCI给了我这个错误：

ProjectEuler4.hs:2:17:
Could not deduce (a ~ ([[a0]] -> [[a0]]))
from the context (Ord a, Num a)
  bound by the type signature for
             projectEuler4 :: (Ord a, Num a) => a
  at ProjectEuler4.hs:1:18-35
  `a' is a rigid type variable bound by
      the type signature for projectEuler4 :: (Ord a, Num a) => a
      at ProjectEuler4.hs:1:18
In the return type of a call of `max'
Probable cause: `max' is applied to too few arguments
In the expression: max palindromeList
In an equation for `projectEuler4':
    projectEuler4
      = max palindromeList
      where
          palindromeList
            = [reverse (x * y) | x <- [1 .. 1000], y <- [1 .. 1000]]

我不知道这意味着什么，并且因为没有找到错误的原因而感到沮丧 . 任何帮助将不胜感激 . 谢谢 .

所以在阅读了一些答案和评论之后，我做了类似这样的事情：

projectEuler4 :: (Ord a,Num a) => a 
projectEuler4 = max' palindromeList
    where palindromeList = [reverse(show(x*y))|x<-[1..999],y <- [1..999]]

max' :: (Ord a) => [a] -> a
max' [] = error "Empty List"
max' [p] = p
max' (p:ps) = max p (max' ps)

仍然无法正常工作 .

好..

按照@ bheklilr的建议，我改变了我的计划：

products :: [Integer] -> [Integer] -> [Integer]
products ns ms = [x * y | x <- ns, y <- ms]

isPalindrome :: Integer -> Bool
isPalindrome n = let s = show n in s == reverse s

palindromes :: [Integer]
palindromes = maximum filter (isPalindrome "") (products [100..999] [100..999])

现在我用什么代替倒置的逗号？我很困惑 .

4 回答

1
第一个重大错误就是你正在打电话
```
reverse (x * y)
```
由于 x * y 是一个数字，并且 reverse 仅适用于列表，因此无法编译 . 您可以使用 show 将数字转换为 String （这是一个列表）：
```
reverse $ show $ x * y
```
但是，反转字符串不是你真正想要做的，你想过滤查找所有的回文，所以你需要通过谓词过滤你的 (x * y) 列表 . 相反，你可以写
```
palindromeList = [z | x <- [1..999], y <- [1..999], let z = x * y, if show z == reverse (show z)]
```
但是，由于这会从屏幕的一侧移开，我建议将其分解为更小的功能
```
-- Generates all products
products :: [Integer] -> [Integer] -> [Integer]
products ns ms = [x * y | x <- ns, y <- ms]

-- Checks if a number is a palindrome
isPalindrome :: Integer -> Bool
isPalindrome n = let s = show n in s == reverse s

-- Generates problem-specific palindromes
palindromes :: [Integer]
palindromes = ??? -- Implementation here.  Hint: filter
```
下一个大问题是因为您正在使用具有该类型的 max 函数
```
max :: Ord a => a -> a -> a
```
但我们真的想找到列表的最大值，所以我们转向 maximum ，它有类型
```
maximum :: Ord a => [a] -> a
```
所以你可以最终确定你的程序
```
projectEuler4 :: Integer
projectEuler4 = maximum palindromes
```
最后一个想法：问题是你需要找到最大的回文，它是2个三位数字的倍数，但是你正在查看的范围是 [1..999] ，其中包括1位和2位数字 . 你怎么办才能检查那些？方便的是，它会使程序更快 .
回复于 2024-04-29T06:22:40+08:00
2
```
Prelude> :t max
max :: (Ord a) => a -> a -> a
```
这是 max 的类型 . 当你在 a 类型的某个参数上调用它时，会得到 a -> a 类型的结果 - 一个函数 . 那是因为通常使用两个值调用 max ;部分应用程序导致一个函数在计算结果之前仍然等待第二个参数，这是两个值中最大的一个 .

该错误显示Haskell已将 palindromeList 的类型推断为 [[a0]] ，因此结果的类型为 [[a0]] -> [[a0]] . 你把它作为 (Ord a,Num a) => a 并且Haskell无法与之匹敌 .

您的意图是使用 maximum ，它处理列表并找到其中的最大值：
```
Prelude> :t maximum
maximum :: (Ord a) => [a] -> a
```
palindromeList 的定义也是错误的 . 首先， [1..999] 中1到99的数字不是三位数字 . 然后你需要测试它们 . reverse (x*y) 当然是错误的： reverse :: [a] -> [a] 但是两个数字相乘的结果是一个数字，但是 - 即使修复它，这仍然不是测试 .

测试类似 show (x*y) == reverse (show (x*y)) .
回复于 2024-04-29T06:22:40+08:00
4
您正试图通过以下方式撤消数字：
```
reverse(x*y)
```
reverse 仅适用于列表 . 幸运的是， String 是一个列表， show 是创建值的 String 表示的规范方法 .

所以尝试类似的东西：
```
reverse (show (x*y))
```
回复于 2024-04-29T06:22:40+08:00
1
您被要求找到两个三位数字的最大产品，即回文 . 该程序将生成一个回文数字列表，并找到该列表的最大值 . 第一步是生成产品的术语，称为x和y . 这是使用生成器 x <- [100..999] 和 y <- [x..999] 完成的 . 注意，如果我们考虑x的特定值，我们只需要考虑y的值大于或等于x;如果没有，我们重复一遍 . 接下来，我们需要确定xy是否是回文 . 完成此操作的最简单方法是将xy转换为字符串，将其调用为s，然后检查 reverse s == s 是否成立 . 为此，请使用 show :: Show a = a -> String . 可以使用函数 maximum :: Ord a => [a] -> a 找到生成的列表的最大值 .
```
euler4 :: Integral a => a
euler4 = maximum [ x * y | x <- [100..999], y <- [x..999], palindromic (x * y) ]
  where palindromic n = show n == reverse (show n)
```
您的代码有几个问题 . 首先， projectEuler4 应该是一个整数值，并且所有整数值都已经是 Ord 和 Num 的实例 . 正确的约束是 Integral a => a . 这将选择 Int 或 Integer . 其次， max :: Ord a => a -> a -> a 给出最大值 Ord 类型类的两个成员，而不是列表中元素的最大值三， reverse :: [a] -> [a] 对列表进行操作，而不是数值;在将 x * y 应用于 reverse 之前，您需要将 x * y 转换为 String . 第四， y <- [999] 表示 y 是从仅包含 999 的单例列表生成的，而不是从 x 到 999 或 100 到 999 的数字列表 .

haskell.org的Haskell教程对列表推导有很好的概述 . 我还会寻找Haskell类型系统的概述，并学习使用交互式GHC环境 - 尤其是命令 :t （如果你是_1583222的类型并且不熟悉标准库） .
回复于 2024-04-29T06:22:40+08:00

Haskell-Project Euler 4

4 回答

相关问题